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 10
9+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!
Is f(x) in every moment is less than or equal to 20 ?
ReplyDeleteIntermediate sums can be arbitrary, but it's not hard to prove that we can always obtain a number between 0 and 9 in the end.
DeleteAn observation is that, if we generate another integer x' by reshuffling decimal digits of a non-negative integer x, we have f(x) = f(x'). For example, f(123) = f(321). The order of digits doesn't matter when using a knapsack-like DP to calculate f(x), so if we only consider 0 <= m < 10^17, the number of distinct DP states should not exceed C(17+10-1, 10-1) = 3124550. With some observation mentioned in analysis, it is enough to only consider these m for building a considerable state space. However, it is still hard to explain why the number of states can be minimized into quite a smaller number than the number above.
ReplyDeletehey Petr, I tried like 5 hours but couldn't figured out, how you manage to get the test dialog in your intellij ide. I found it very useful, please help. Thanks
ReplyDelete