A week with two rows

On the Mar 13 - Mar 19 week, VK Cup 2017 started with its Round 1 (problems, results, top 5 on the left, parallel Codeforces round results, my screencast of the Codeforces round with commentary, analysis). Congratulations to Zlobober and zemen on the win!

I've made a second attempt at explaining myself to the camera during the competition, and this time it it went even worse. I've managed to implement an incorrect solution for C before realizing it and rewriting from scratch, and if that wasn't bad enough followed up with doing the same - implementing an incorrect solution that needs to be dropped on the floor - twice for problem D. Maybe talking is indeed incompatible with critical thinking?..

Here is problem D that has stopped me in my tracks. You are given a grid with two rows and n columns, each cell containing a (not necessarily positive) integer. Your goal is to find as many non-intersecting rectangles on this grid as possible, such that each rectangle has a sum of 0. n is up to 300000.

In my previous summary, I have mentioned a cute AtCoder problem. You are given a huge number n with at most 500000 (decimal) digits, and need to find the smallest number k such that n can be represented as a sum of k numbers with non-decreasing decimal representation (for example, 1157888).

The approach I talk about in my screencast is a bit vague, and I like the approach from the editorial more. First, we notice that numbers with non-decreasing decimal representation are exactly those numbers that can be represented as a sum of 9 numbers which consist only of ones (like 1 or 1111; we will also count 0 as such a number with zero ones) - the main Young diagram trick strikes back :) So our goal is to represent n as a sum of 9k such numbers.

Each such number is equal to (10^m-1)/9 for some m, so we actually need to represent 9n+9k as a sum of exactly 9k numbers of form 10^m. The smallest amount of such numbers needed to achieve 9n+9k is naturally given by the sum of digits in the decimal representation of 9n+9k, and is divisible by 9. We can then repeatedly replace a power of 10 with ten smaller powers to get any bigger amount divisible by 9, up to 9n+9k (when the sum is all ones). We need to achieve 9k which is also divisible by 9, so we just need to check if the sum of digits in the decimal representation of 9n+9k is less than or equal to 9k.

Now that we know how to check any given k, we can use binary search to find the minimum possible value of k. Voilà!

Thanks for reading, and check back soon for the last week's summary.