Wednesday, December 17, 2014

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(N3), but this problem required a O(N2) 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(N3/logN). However one had to find one more speedup and solve the problem in  O(N3/log2N) - 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(N2) 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(N2) 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(N2) 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!

Monday, December 8, 2014

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!

Sunday, November 30, 2014

This week in competitive programming

This week was relatively calm, with just one contest: TopCoder SRM 639 (problems, results, top 5 on the left, my screencast). The screencast is quite evenful in its second part: at 57:30 in the screencast, I was at the top of the standings with all problems solved and 1304 points, and was about to relax until the end of the contest. But then I've decided to quickly write a stress test comparing the output of my solution for the 1100 problem with the output of a simple-but-slow solution, and that changed everything. I've found that my solution had a bug, had to diagnose and fix it quickly (it turned out to be very very stupid, of course), and then had to go all-in at the beginning of the challenge phase with blind challenges.

All challenges were on the easy problem, which went like this: two players are playing a game with several rounds. The winner of the first round gets 1 point, the winner of the second round gets 3 points, then 5 points, and so on. Given two numbers x and y, is it possible that after some number of rounds the first player has x points and the second player has y points? If yes, then what is the smallest number of rounds the first player could've won?

If the scores for the rounds were 1, 2, 3... instead of 1, 3, 5, ..., then there would really be no corner cases and no challenge opportunities. However, the use of odd numbers resulted in a few tricky situations, in particular no player can score exactly 2 points now, and thus many greedy algorithms failed. In fact, just 138 out of 496 submitted solutions turned out to be correct. Can you see how to overcome this difficulty?

In addition to hosting the SRM, TopCoder has uploaded the TCO 2014 "Epilogue" video this week — check it out!

The ACM ICPC North-Western European Regional Contest happens today, most other European ACM ICPC regionals happened earlier, with the sole exception of the Russian and ex-USSR regional NEERC which takes place next Sunday. I will try to summarize the results of all European regionals in the next week's summary, so check back in 7 days!

Monday, November 24, 2014

This week in competitive programming

I've already covered the results of the TopCoder Open 2014 in my earlier posts (first, second), which was one the biggest tournaments of the year and certainly the things will now quiet down a bit before 2015. Coincidentally, last week witnessed the finish of a similar long-running sporting event: the World Chess Championship. It might not be entirely accurate to draw parallels between competitive programming and chess because the chess grandmasters use a much more highly specialized skill compared to the somewhat general abstract thinking required to come up with new algorithms at contests. Nevertheless, last night's game 11 of the championship was reminiscent of the challenge phase of the TCO: at move 27, Anand decided to go for an exchange sacrifice since the game was heading into a draw otherwise, and he just wanted to add more randomness to the result. In a similar fashion, it seems pretty obvious in hindsight that I should've made a couple quick challenges in the beginning of the TCO finals challenge phase since I didn't have anythng to lose but had so much to gain if at least one was successful. It didn't work out for Anand, and would not work out for me as well, but he did at least try :)

A couple of days after the TCO, Codeforces Round 278 continued the competitive week (problems, results, top 5 on the left). Top 3 in this round have all been at TCO in different roles - a Marathon finalist, an Algorithm problemsetter, and an Algorithm finalist. Congratulations to Tiancheng on the victory in his first algorithm round after a 3-month break!

Finally, Open Cup 2014-15 Stage 4 took place on Sunday (results, top 5 on the left). The two teams that seem to be the strongest Russian ACM ICPC teams this year have swapped places once again at the top, ITMO 1 claiming the top spot with a very respectful margin over the Tapirs. The Open Cup season will now take a 3-week break as Russian ACM ICPC teams prepare for the NEERC (North-Eastern European Regional Contest) that takes place on December 7.

I've skipped this Open Cup round because I got stuck in Chicago for almost 24 hours on my way back from the TCO due to some technical difficulties with the plane. At the same time, this allowed me a chance to take a walk in Chicago (I've never been there before) and see how real winter looks in the United States as the temperature was well below the freezing point. Well, it's all nice and friendly!

Thanks for reading, and check back next week!

Thursday, November 20, 2014

TCO 2014 Algorithm Finals day

TopCoder Open 2014 Finals have concluded earlier today (results with statements accessible by clicking the point value, top 5 on the left). Gennady has completed his full sweep of 2014 trophies, while I came in second place. Looking back at how the contest went, there were several ways I could've squeezed the first place:
  • I could've solved the 1100. This is the most obvious way, and yet the most difficult since it's still not clear to me how long the solution would take to write. The problem itself had very simple and beautiful statement: given the integer scores of N (up to 500000) teams, calculate the number of possible rankings if the score of each team either stays the same or increases by exactly 1, and ties a broken by the team number. The basic idea for the solution is also quite straightforward: there are 2N ways to either add 1 to each score or not, and it takes quite specific conditions for two different sets of scores to lead to the same ranking, so we should carefully avoid counting those specific cases. However, the devil is in the details - I had most code ready by the end of the coding phase, but it's still not clear how long it would take to debug it. Because of that, we don't know if opening the 1100 earlier would've lead to better or worse results, so we can't tell which strategy was better this time :)
  • I could've found one more challenge than Gennady. I've actually found the issue in bmerry's 550, but somehow hesitated to challenge, which was clearly a mistake. But in order to find the second challenge I had to beat Endagorion or tourist on one of the 350 challenges, and it was quite hard since I was reading the 350s in the wrong order: from highest score to lowest.
  • I could've spent less time on the 550. Somehow analyzing the problem on paper took a very long time, even though there was no algorithmic difficulty: the standard approach for solving such problems, considering what happens if we swap two adjacent instances, worked very well.

(Picture on the left from the TopCoder website: spectators are watching the coding phase)

Well, better luck next time :) Misof has written his awesome commentary for the finals, go check it out! And of course, check back in the beginning of next week for the weekly summary.

Wednesday, November 19, 2014

TCO 2014 Algorithm Semifinals day

Today was a long day for the Algorithm competitors at the TopCoder Open. It started at 9am with Semifinal 1 (results with statements accessible by clicking the point value, top 5 on the left). The medium problem was the highlight of the round for me: you were given a single number N up to 1018, and were asked to come up with any (unrooted) tree that has exactly N automorphisms and at most 200 vertices. First, one has to think how to find the number of authomorphisms of a tree, and discover that it's always a product of several factorials  Then, you need to find a way to represent N as a product of several factorials. And finally, one had to construct a tree with the given "degree of freedom". All in all, instead of just coming up with one brilliant idea that solves the problem immediately, here you have to analyze and use your creativity several times to arrive at a working solution.

Another interesting aspect of this semifinal is the strategy battle. Lyrically has followed his usual hard-easy-medium approach, and that gave him an edge over the standard easy-medium-hard strategies of other contestants who didn't manage to solve all three.

Semifinal 2 took place four hours later at 1pm (results with statements accessible by clicking the point value, top 5 on the left). Once again, going for the hard has turned out to be a good idea as Endagorion has pushed Egor down to the Wildcard round.

The Wildcard Round followed at 6:30pm (results with statements accessible by clicking the point value, top 5 on the left). This time going after the hard problem didn't work out for qwerty787788, but he only went for it afer unsuccessfully solving the medium for quite some time — so maybe he could've qualified if he had started with the hard?..

Overall, I feel like today's rounds point in the direction of opening the hard problem earlier than usual. The benefits are quite tangible: in case there's no time to solve all three, it's better to have easy+hard than easy+medium. And in case the hard is completely unsolvable, you will probably have guessed that after 30 minutes or so, and by that time you can look at the scoreboard to estimate how much time one needs to solve easy+medium, to avoid fighting with the hard for too long. The risks are slightly increased, too: it might happen that you need a bit more time than average for easy+medium, and will be left with just the easy. Alternatively, you might overestimate your ability and keep pushing the hard hoping to get it in time and fail afterwards.

What is the strategy you think I should use tomorrow in the Finals? Please vote in my Google+, and present your reasoning in comments if it differs from the above!

Just 8 contestants are left standing in the TCO: bmerry, Egor, Endagorion, lyrically, Petr, tourist, wata, WJMZBMR. The Finals happen tomorrow, November 19, at 1pm Pacific time. There will probably be live coverage in Misof's blog, which already has awesome commentary on today's semifinals — go check it out! And of course, check my blog tomorrow for the news after the finals end :)

Tuesday, November 18, 2014

This week in competitive programming

Open Cup 2014-15 Stage 3 was the only contest of the week (results, top 5 on the left). The Tapirs team from the Moscow State University have shown once again that the ITMO 1 team is not impossible to beat this year. Congratulations!

Problem B was a beautiful exercise of combining several well-known ideas into a good solution. You were given a road network of some mythical country represented as an undirected graph with at most 200000 nodes and edges, with each edge having a length in kilometers. Some nodes were special — they contained petrol stations. Then, you were given a series of at most 200000 requests of the form "Is it possible to get from node A with a petrol station to node B with a petrol station using a car that is capable of traveling at most C kilometers without refueling?" for different values of A, B and C. Can you answer all those requests using just 2 seconds of CPU time in total?

Late on Sunday, the TopCoder Open 2014 (official blog, official photos) started in San Francisco. You can see the introductory video to the left, configured to start right where TopCoder Open victories are compared to the Moon landing :) But you can of course watch it from the beginning, it's just over 1 minute in length.

The organizers have decided to take advantage of the nicely competitive algorithm competition format, and added several more algorithm rounds to entertain the spectators. On Sunday, the Celebrity Algorith Match gathered 8 past greats. Each competitor has nominated a charity, and the charity of the winner would get the $10000 prize. You can guess the winner from the picture on the left :)

Four "Pickup Algorithm Rounds" where all spectators can participate are also on the schedule. I guess the original idea might've been to get the spectators from the "outside world" interested in algorithmic programming contests, and it's working to some degree as people with completely new TopCoder handles are taking part. The top of the standings, however, is still taken by people with "target" rating working for different companies in the Bay Area :)

Monday is the Marathon day, with 12 finalists competing for 12 hours trying to design the best possible route for a plane putting out a forest fire. You can pretty much understand the problem from this video showing one of the solutions at work. The current standings change often, and the margins are not too slim, suggesting that the final round problem was once again picked perfectly: enough ideas to explore in 12 hours, yet very easy to get going and with wonderful visualization. Great job!

Thanks for reading, and check back tomorrow for the news about Algorithm semifinals. Please ask any questions you might have about the TCO in comments!