This week in competitive programming

2014 is coming to an end, but the algorithmic competitions are still in full swing. Codeforces Round 284 happened on Christmas Eve (problems, results, top 5 on the left). Top 5 is full of usual suspects, and this time Egor Suvorov is on top - congratulations!

TopCoder SRM 643 picked up the competitive spirit right after the Christmas holidays (problems, results, top 5 on the left). Both the easy and the medium problems required ad-hoc solutions that were easy to get wrong - I got trapped twice, resubmitting both problems - so the round was decided during the challenge phase. zerokugi and wleite achieved amazing +425 points from challenges each (9 successful + 1 unsuccessful), but zerokugi also got both problems correct and claimed the first place - awesome performance!

The easy problem asked you to factor a number up to 10¹⁸ into a product of primes, but with some extra help: you were already given every other factor in sorted order, starting from the smallest factor, then the 3rd smallest factor, and so on. The most probable mistake here was accidentally doing 10⁹ operations for a tricky testcase and thus running out of time.

The medium problem studied a table zeroes and ones with two rows and at most 200 columns. In one operation, you could either change a single element to be equal to one of its adjacent elements by row or column, or change an entire column to be equal to one of its adjacent columns, or change any horizontal contiguous segment in one of the rows to be equal to the corresponding segment of another row. In this problem there are a lot of different correct greedy and dynamic programming solutions, but even more different incorrect greedy and dynamic programming solutions.

I was aware that both problems were tricky before the challenge phase. Given that I knew only one way to fail the first problem, and a lot of ways to fail the second problem, I've decided that it would be much easier to look for the mistake in the first problem and tried to challenge those solutions. In hindsight, this was obviously a wrong decision, for the following reason: despite there being many possible mistakes in the second problem, every mistake means that we're handling some small pattern incorrectly. So if we take a random 2x200 table, it will most probably contain the corresponding bad pattern for every possible mistake, and we can just challenge all solutions blindly and very quickly without actually finding what each mistake is.

It seems that making good logical decisions for the challenge phase is still tough for some reason :) Thanks for reading, and check back in 2015!

This week in competitive programming

Just two rounds happened this week, both on Wednesday. The first was TopCoder SRM 642 (problems, results, top 5 on the left). Given that the total time between the start of the SRM at 5am Moscow time and the end of the following Codeforces round at 9:30pm Moscow time was 16 hours 30 minutes, it was quite hard to participate in both while maintaining a healthy sleep schedule, so I've passed on the SRM :) Nevertheless, anta showed that my fears were unfounded by winning the SRM and placing fourth in the Codeforces round - great job!

Codeforces rounds with problems by Endagorion are becoming a trademark of their own because of interesting and diverse problems, and Round 283 was no exception (problems, results, top 5 on the left, my screencast). Baz93 claimed the first place thanks to the super-fast solution for problem D. You were given two (not necessarily convex) polygons, each rotating around a point with the same angular speed in the same direction (those rotation centers could be different for the two polygons, and could be outside the corresponding polygon), and needed to determine whether they will ever intersect or touch. Each polygon had at most 1000 vertices. The problem requires both a geometrical insight, and some computational geometry mastery - can you see the insight?

I was going to describe the solution to the Open Cup problem discussed in last week's summary, but I was beaten to it in comments by +Ilya Kornakov and +Andrey Kolosov, so you can check them out instead :) The other problem mentioned in last week's summary, about counting triangles containing the origin, was solved in NlogN using the following insight: instead of counting triangles containing the origin, let's count the triangles NOT containing the origin. Each of those triangles is contained in some half-plane containing the origin, so if we rotate the half-plane slowly, then every time a new point arrives in the half-plane, we should increment the result by (n-1)*(n-2)/2, where n is the current number of points in the half-plane, thus accounting for all triangles containing the newly arrived point.

Thanks for reading, and check back next week!

This week in competitive programming

TopCoder SRM 640 (problems, results, top 5 on the left) opened the week's competitions on Tuesday. Three "targets" participated in the round but they couldn't get into the top 5, while the winner Zero_sharp was just 31st by rating going into the round, and got the first place (and became 16th by rating among the participants) thanks to the challenge phase performance - congratulations!

TopCoder SRM 641 (problems, results, top 5 on the left, my screencast) happened at almost the same time two days later. This time tourist took no chances with great coding phase performance and two successful challenges to boot. The victory also allowed him to claim the first place in the TopCoder ratings - congratulations!

The easy problem in this round featured a well-known, but still beautiful, trick. You were given N points on a plane, and needed to count how many triangles with vertices in those points contain point (0, 0) inside them. This is of course very easy to do in O(N³), but this problem required a O(N²) solution. Many contestants went a step further and solved it in O(NlogN) - can you see that improvement?

Codeforces Round 282 (problems, results, top 5 on the left) gathered the best algorithmists on Saturday. Only two contestants - tourist and Endagorion - managed to solve the hardest problem E, but tourist has added three more correct problems and three successful hacks to win the round with a big margin - congratulations once again!

On Sunday, OpenCup 2013-14 Stage 5 (problems, results, top 5 on the left) became a contest where tourist's team participated but didn't win, for a change, although they were very close with two more problems solved but not accepted.

One of those problems, problem I, went like this: you were given three polynomials f(x), g(x) and h(x), defined over Z/2Z (remainders modulo 2), each polynomial's power was at most 4000, and needed to compute another polynomial: f(g(x)) mod h(x). Polynomials over Z/2Z are just sequences of bits, and thus it's not hard to see how to use bitwise operations to perform this task in O(N³/logN). However one had to find one more speedup and solve the problem in  O(N³/log²N) - and I think this is a very instructive problem to teach those speedups, so I encourage you to look for that solution.

Finally, let's go back to NEERC's problem E from the last week's summary. To remind, it was centered around the Rock-paper-scissors game. You were given a description of a finite-state machine where each state has one move associated with it (rock, paper or scissors), and three transitions corresponding to three possible moves of the opponent. The initial state of that machine was unknown. You had to create another finite-state machine in the same format that would beat the first machine at least 99% times in the long run, irrespective of the first machine's initial state.

Suppose we know the initial state of the first machine. Then beating it 100% of the time is very easy: we create a machine with the same number of states as the first machine, each state has the winning move for the corresponding state of the first machine (rock for scissors etc), and we actually care about just one transition out of three for each state: the one that happens when we win - we should transition to the state corresponding to the state the first machine transitions when it loses.

But we don't know the initial state. Let's assume the initial state is state 1, and build the above always-winning machine. What will happen if the initial state was in fact state 2? Well, since we know the first machine, we can emulate the process. One of the two things can happen: either we still win 100% of the time (this can happen, for example, if states 1 and 2 of the first machine are isomorphic), or we lose at some point. When we lose, our machine reaches a transition that we haven't yet defined. What we can do now is to add another N states to our machine with the same transitions between them that lead to always winning if we're in the right state, and direct the "losing" transition we just encountered to the appropriate state of those N, so that we would lose just once if the initial state was state 2.

We can now do the same with state 3, with a small difference: when we lose, it might happen that we lose for the first time in the same way as we did with state 2. In this case the "losing" transition is already defined, and we can't override it for state 3. In this case we should continue playing until we lose again (or make sure we never lose anymore, in which case we're fine), and this time we would be using the second set of N states and thus the first losing transition will be undefined and we'll be able to add another N states to take caret of initial state 3 of the first machine.

Doing the same for all states of the first machine, we obtain a finite state machine that has at most O(N²) states and loses at most N-1 times for any initial state of the first machine, where N is the number of states of the first machine.

There are still several questions that I don't know the answer for. Is it possible to build a machine with less than O(N²) states? If not, then what's an example first machine that requires so many states?

Finally, let me describe a slightly different solution to the contest problem that was used by many teams at the NEERC. Since it's easy to construct the finite state machine that always wins if we know the initial state, let's simply do the following: whenever we lose, let's just jump to a random state. Then sooner or later we'll jump to the appropriate state by luck and will keep winning ever since. Of course, the finite state machines don't allow random jumps. If we pick a random but specific jump for each losing transition, this will not be good enough, since those jumps might form a loop quite easily. To combat that, let's make several copies of the winning machine, for example N copies to have the same O(N²) states as the previous solution did, and assign different random jumps for losing transitions out of each copy. This way the chance of accidentally forming a loop from losing transitions is much lower, and we'll most likely randomly reach the correct state at some point.

This raises another question which I don't know the answer for: is it possible to actually estimate how likely is this solution to pass?

Thanks for reading, and see you next week!

This week in competitive programming

There were no big online contests this week, but the last and strongest European ACM ICPC regional, the NEERC, happened on Sunday (problems, results, online mirror results, top 5 on the left). The two favourites, SPb ITMO 1 and Moscow SU Tapirs, did not disappoint - congratulations!

I've set problem G together with pashka. You can find the full statement on page 9 of the PDF, but the general idea was that you had to write a program that would always win as the second player in Gomoku against a pretty weak strategy. Of course, since the first player has a guaranteed win in this game, the strategy you're playing against has to be weak. More precisely, the strategy considered all possible moves, and evaluated the resulting position for each move, picking the move that leads to the best position modulo some random noise. When evaluating a position, the strategy considered each horizontal, vertical and diagonal of five cells, and tried to minimize the number of such rows where the other player has four marks and it had none. To break ties, it tried to maximize the number of such rows where it had four marks and the other player had none. To break ties again, it tried to minimize the number of rows where the other player had three marks and it had none, and so on.

The ITMO 1 team made the biggest progress in this problem, creating a strategy that won about 95% of the games. However, you had to win 100 games in order to get this problem accepted, and the chance of that was around 0.5%, and they didn't get so lucky. Here are three short videos: ITMO 1 winning a game, ITMO 1 losing a game, and the reference solution - spoiler alert! - winning a game (in all cases the contestant's strategy is playing blue circles):

    

I've also enjoyed problem E a lot - see the full statement on page 7 of the PDF. It was also centered around a game, this time a much simpler one: Rock-paper-scissors. You were given a description of a finite-state machine where each state has one move associated with it (rock, paper or scissors), and three transitions corresponding to three possible moves of the opponent. The initial state of that machine was unknown. You had to create another finite-state machine in the same format that would beat the first machine at least 99% times in the long run, irrespective of the first machine's initial state.

Can you see how to do it? How many states does your machine need in the worst case if the input machine has N states? Can you prove that such number of states is asymptotically minimal? Can you see a simple randomized solution with the same number of states?

You can try to submit those two problems, as well as 9 others, at the online mirror.

All other European regionals are also over by now: the SEERC (problems, results), the CERC (problems, results, Russian training camp mirror results), the SWERC (problems, results, online mirror results), and the NWERC (problems, results, online mirror results). Congratulations to Lviv NU Penguins, University of Zagreb, UPC 1 and University of Copenhagen Lambdabamserne on the victories! The intersection between different online mirrors is rather small, but the general feeling is that the two top NEERC teams are the strongest in Europe this season.

Thanks for reading, and check back next week!