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 -

Here is problem D that has stopped me in my tracks. You are given a grid with two rows and

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

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 9*k*such numbers.
Each such number is equal to (10

Now that we know how to check any given

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

^{m}-1)/9 for some*m*, so we actually need to represent 9*n*+9*k*as a sum of exactly 9*k*numbers of form 10^{m}. The smallest amount of such numbers needed to achieve 9*n*+9*k*is naturally given by the sum of digits in the decimal representation of 9*n*+9*k*, 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 9*n*+9*k*(when the sum is all ones). We need to achieve 9*k*which is also divisible by 9, so we just need to check if the sum of digits in the decimal representation of 9*n*+9*k*is less than or equal to 9*k*.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.

## No comments:

## Post a Comment