Sunday, May 3, 2020

A 2021 week

TopCoder Open 2020 Round 1B was the first round of this week (problems, results, top 5 on the left, parallel round results, analysis). This was the last chance to get into Round 2 for those who have not qualified yet, and the problemset was correspondingly even more on the easier side. It turned out that a nonzero score was enough to advance, so contestants were mostly competing against the problems instead of between themselves. In order to get the first place, however, one required a few successful challenges as well. jzd got three and won — congratulations!

Google Code Jam Round 1C followed on Saturday (problems, results, top 5 on the left). Just like in the TCO round, this was the last chance to get into Round 2, but the competition was more intense: one needed to solve at least the first two problems completely to advance, and do it in about one hour. Just half an hour was enough for all three problems for Rafbill and maroon, and Rafbill held to a 4-second edge to claim the win :) Well done!

Finally, Open Cup 2019-20 Grand Prix of Nanjing wrapped up the action (results, top 5 on the left, analysis). Team NNSU Almost Retired claimed their second win of the season and seem to be in great form — congratulations! It looks like they'll need to maintain the form for quite a bit longer, as ICPC 2020 World Finals got rescheduled to 2021. Team USA1 got 11 problems as well, but an enormous amount of incorrect attempts has ruined their penalty time.

Problem B was very easy for some teams, but we got stuck on it for the whole contest, only to come up with a solution right after the end :) It went like this: we have a string which is initially empty. Then we repeatedly add characters either to the beginning of the string, or to the end of the string, n times (n<=1000000). Then, we need to print n numbers: how many period lengths did the string have after each addition? A string s has a period length k if 1<=k<=length(s) and for each valid i si=si+k (note that under this definition the last repetition of a period may be incomplete). For example, the string ababa has 3 period lengths: 2, 4 and 5. Can you see the trick?

Thanks for reading, and check back next week!

1 comment:

  1. Hi Petr! I admire your work and the efforts you put behind these blogs.
    It's been two weeks now since the last post (I've been checking daily since last to last Monday). Hope you can bring the latest blog post soon.