This week in competitive programming

The week's events started with TopCoder SRM 623 (problems, results, top 5 on the left) at 5am Moscow time. Many of recent Moscow 5am SRMs have still been unexpectedly won by Russians despite the lack of sleep, but this time we got the more natural result - Mark from the United States claimed the top spot, congratulations! This was his second SRM win after almost five years delay - the previous one was SRM 447 back in August 2009.

On Friday, Yandex.Algorithm 2014 Round 2 took place (results, top 5 on the left, my screencast). The problems were more difficult than in the first round, but the optimal strategy was the same - submitting one or two problems blindly (and correctly) was enough to get a place that guarantees or almost guarantees a spot in the onsite round in Berlin.

TopCoder Open 2014 Round 2B selected another 50 lucky contestants on Saturday (problems, results, top 5 on the left). Looking at the advancers from rounds 2A and 2B by country, the top 5 countries are Russia - 25 contestants, China - 17 contestants, and Poland - 10 contestants. Last year at the same point the top 3 countries were the same, but there were 34 advancers from Russia, 12 from China and 10 from Poland - so the Chinese have made the biggest progress this year (and Russians have the biggest fall).

At the same time, the 50 advancers from Round 2A could solve the same problems in an alternative round called TopCoder Open 2014 Parallel Round 2B (results, top 5 on the left, my screencast). However, there was yet another option for people who advanced from Round 2A: they could set problems for Round 2B - and tourist did exactly that, setting the easy and the hard problems. The easy problem was a pretty greedy: you have N lamps, each lamp can be on or off, and you want to iterate through several states of the lamps in order. Each of the states describes the state of all lamps: on, off or doesn't matter. When switching from one state to another, you can switch lamps off or on, and you spend 1 minute if you don't touch any lamps, 2 minutes if you only switch some lamps on or only switch some lamps off, and 3 minutes if you do both switching on and switching off. What is the smallest time needed to iterate through given states in given sequence?

And finally, Russian Code Cup 2014 became the first competition of the current bunch to select its onsite competors in the final online round (problems, results, top 5 on the left, my screencast). 50 top finishers will come to Moscow in October for the championship round, and also receive nice gifts from the organizers: three years ago it was an iPad, two years ago it was Lego Mindstorms, and last year it was AR.Drone 2.0. Last two gifts are good examples of things software engineers will likely not buy for themselves, but are very happy to play with - so they are very good as such gifts, in my view.

The hardest problem of the round had a very simple statement: you are given two cells on an infinite grid, (x1, y1) and (x2, y2). You need to move the robot from (x1, y1) to (x2, y2) in exactly t turns, where each turn consists of moving the robot from a cell to one of its 4 adjacent cells. You're not allowed to move the robot to cells where at least one coordinate is zero or negative, and you're not allowed to visit (x2, y2) before the t-th turn. How many ways are there to achieve these goals? All five numbers in the input are up to 250000.

The problem statement also had the following clause, not very important at first sight: output the answer modulo 998244353. Many combinatorial problems ask for an answer modulo a large prime number, to allow contestants to operate within the range of the programming language's integer types. But in most cases the modulo is 1000000007 - a billion plus seven. Here, the modulo was unusual, and it was actually a very strong hint towards the solution. Not only is 998244353 a prime number, the number that is 1 less divides by a large power of two: 998244352=2²³*7*17. Why is that important? It means that there's some number X such that X²²³ = 1 (mod 998244353), and X²²² != 1 (mod 998244353). And that, in turn, allows the Fast Fourier Transform to work over remainders modulo 998244353 for polynomials of degree up to 2²³, which is conveniently greater than 250000.

Can you see how Fast Fourier Transform helps in this problem?

Thanks for reading, and see you next week!

Tweet