TopCoder SRM 809 was the first event of the last week (
problems,
results, top 5 on the left,
analysis). This was apparently the first SRM that counts towards
the TCO22 qualification, and I have completely overlooked this fact and did not prioritize participating :( Congratulations to those who pay attention, and especially to tourist on solving the hard problem almost twice faster than everybody else and thus earning the clear first place!
The VK Cup 2021 Elimination Round for those who speak Russian and qualified, which was also available as Codeforces Round 733 for everybody else, followed on Saturday (
problems,
results, top 5 on the left,
parallel round results, top 5 on the right,
analysis stream,
analysis). Everything went pretty well for me in this round, I got the solution ideas quickly and only had to do heavy debugging once, in problem G. However, Um_nik chose a superior strategy and went for problem H in the end which gave him much more points, and won the round. Well done!
More worryingly for me, despite me feeling pretty good about my performance on the first six problems, some usual suspects in the parallel round were faster to solve those six problems and managed to solve both harder problems to boot! Congratulations to jiangly and ecnerwala. It seems that just having a good day is no longer enough for me to compete for the first place at Codeforces :)
The hardest
problem H was a pretty nice example of DP optimization. You have a tape that is infinite in both directions and is split into cells. You're going to write a given
random permutation of size
n<=15000 onto this tape in the following manner: you write the first number somewhere, then you either stay in the same cell or move one cell to the left or to the right, then write the second number there, then again either stay or move to an adjacent cell, write the third number there, and so on. Whenever you write a number into a cell that already has a number, the old number is overwritten and therefore discarded. After all
n numbers have been written, we look at the resulting sequence written on the tape from left to right. What is the maximum possible size of an increasing subsequence of this sequence? Note that the given permutation is guaranteed to have been picked uniformly at random from all permutations of size
n (which conveniently makes preparing the testcases for this problem so much easier!)
Thanks for reading, and check back next week!
