Sunday, March 29, 2015

This week in competitive programming

TopCoder SRM 654 took place in the early hours of Thursday (problems, results, top 5 on the left). Less than half a year after winning an SRM for the first time, Endagorion has now earned his third SRM victory, a feat accomplished by just 50 contestants in the history of TopCoder - congratulations! Next step would be to become the 32nd person to win four SRMs, of course :)

Russian Code Cup 2015 Qualification Round 1 happened on Saturday (problems in Russian, results, top 5 on the left). This was the strongest qualification round since top 200 have qualified and will thus be unable to participate in the next two qualification rounds. Congratulations to Gennady on another flawless victory!

The last problem is worth mentioning at least for its very simple statement: how many strings of length n are there with the given value of a polynomial hash? n is up to 106, the polynomial hash is computed with the given base p and modulo m, m is up to 104 (more precisely, the hash is equal to a0+a1*p+a2*p2+... mod m, where ai is the i-th character of the string, which consists only of lowercase English letters). You need to output the answer modulo 998244353.

Finally, Open Cup 2014-15 Grand Prix of America happened on Sunday as usual (results, top 5 on the left, results of another contest with the same problemset but different time limits). One of the tricky problems, problem G, was about constructing a long string s using a short string t. We start with just the string t. Now we insert another occurrence of t anywhere (possibly before the first or after the last character), and repeat this process until we obtain string s. In the sample input, s was "hhehellolloelhellolo" and t was "hello". Given the string s with at most 200 characters, what's the shortest string t that could've been used to construct it?

Thanks for reading, and see you next week! Please also find a photo with a spring - if a bit gloomy - feeling on the left :)

No comments:

Post a Comment