## Monday, March 11, 2019

### A painful week

TopCoder SRM 752 was the first round of the last week (problems, results, top 5 on the left, analysis). rng_58 maintained his advantage in the race for the third TCO19 spot and was quite close to increasing his lead even further as he was just 4 points behind the first place before the challenge phase, and pashka was outside the top 10. However, tourist found 100 challenge points and won (congratulations!) and pashka found 50 challenge points and jumped into exactly 10th place, meaning that both rng_58 and pashka got 4 tournament points for this round.

Codeforces held its Round 545 early on Friday (problems, results, top 5 on the left, analysis). Only sunset was able to solve very tricky problem F, so even exceeding the memory limit in problem C (thanks to implementing an asymptotically optimal solution but with a huge constant both for time and memory) did not change the outcome. Congratulations on the win!

Open Cup 2018-19 Grand Prix of China wrapped up the week (results, top 5 on the left, analysis). All problems were solvable in this round, but all of them required quite a bit of thinking and quite a bit of coding, and also, as zeliboba quite succinctly formulated, had a few somewhat unnecessary corner cases. Team Past Glory still prevailed in those tricky conditions with the last problem accepted at 4:59. Well done!

Problem E in this round reminded me of my earlier post where I tried to describe a way to find dynamic programming states semi-automatically. The problem went like this: let's define f(x) as the smallest non-negative number that can be obtained by placing + or - before each digit in the decimal representation of x, and computing the resulting sum. What is the sum of all numbers x between l and r  that have f(x) equal to 0, 1, ..., 9, modulo 109+7? l and r have at most 100 digits, and there are 10000 testcases to solve in 2 seconds.

The idea to use dynamic programming is on the surface, but it's completely unclear how to achieve a manageable number of states. Do you see a way to find a small state space algorithmically?

Thanks for reading, and check back next week!