Monday, November 16, 2015

An educational week

I've already shared my impressions about the TopCoder Open 2015 Semifinal and Final rounds; however, this week had another noteworthy event:

Educational Codeforces Round 1 has tried to realize the "only solutions that can truly handle all possible cases should score points" aspiration by allowing 24 hours of challenges, including the ability to stress-test, after the round has ended (problems, results, top 5 on the left, experiment descriptionexperiment analysis). I haven't been participating myself, but from the surrounding blogs it looks like the experiment was quite successful, with many contestants contributing tricky testcases after the round has ended. What are your impressions from this format?

Thanks for reading, and check back next week!

A pre-week

After the TCO dust has settled, let's take a quick look at the pre-TCO week.

Open Cup 2015-16 Grand Prix of Siberia took place on Sunday (problems, results, top 5 on the left). In yet another reshuffle of top Russian teams, the SPbSU Base team got the top spot thanks to almost flawless correctness stats: only one incorrect submission per 11 problems! Such clean stats were once the trademark quality of another famous SPbSU team, the SPbSU 4 that won the world championship in 2014 (for example, here are the stats of the last Petrozavodsk training camp before the said world championship - the "Dirt" column is the fraction of incorrect attempts to correct attempts), so the SPbSU Base team has picked the right example to follow :)

Wednesday, November 11, 2015

An 8-connected day

TopCoder Open 2015 Finals concluded yesterday (problems, results, also on the left, editorial, discussion). This round had a few extremely nervous moments and a happy ending. It started in a usual manner with a 250 that's not difficult algorithmically but requires careful coding. After submitting it in about 10 minutes, I had to choose whether to go for the 600 or for the 1000. Without tourist in the final round my motivation for alternative strategies was much weaker, as increasing the variation at the expense of the expectation was not desirable. Kuniavski has submitted the 250 with higher score than myself, so there was still some motivation to go for the 1000, but I've still decided to go with the 600 hoping to beat kuniavski by solving it faster than him. This problem has later resolved itself because he has resubmitted his 250 for a much smaller score.

That's where things stopped going so smoothly. For quite some time, I had no idea how to solve the problem. After experimenting with a few testcases on paper, I had a plan: each 8-connected set of obstacles has to have a very specific form, and we can determine the direction of jumps along its boundary uniquely. That, in turn, lets us determine the direction of jumps one square further diagonally, and so on, so now we need to check whether those "projections" from different 8-connected sets of obstacles contradict.

This was possible to implement in the remaining time, but it would be extremely error-prone, so I've started the implementation with a random testcase generator and a maximum matching based slow solution to compare with. I've continued to implement the actual algorithm, and with about 10 minutes to go I had it passing the testcases from the problem statement, and most of 1000 randomly generated cases - but not all of them.

I've debugged a failing case on paper, and realized that my logic that checks for contradictions between projections is not strict enough. It was not clear how to fix it properly, and there was about 5 minutes remaining in the round at this point, so I've decided that my solution is probably completely wrong and started to re-read my 250 solution to check for errors.

But then, with about 2 minutes to go, qwerty787788 has submitted his solution for the 600, jumping to the first place. That has switched me to a different mode of thinking: what's a possible fix for my solution for the 600 that I could implement in 2 minutes? I've decided to try making the contradiction checking logic more strict by simply commenting out the specific part of code that caused no contradiction to be reported in the failing case - and was extremely surprised to see the new solution pass all 1000 randomly generated cases! It was extremely important to have the testcases and the testing framework ready by then, as everything happened in a matter of seconds, and I submitted my solution with about 20 seconds to go in the coding phase.

(Photo on the right from the official website) After the coding phase ended, I've ran my solution on 9000 more random cases - and it failed one or two of them :( Because of this, I was quite certain that my 600 solution would fail the system test, and thus started preparing for the challenge phase under the assumption that I have only 225 points. Having debugged my solution a day later, I know that the only bug was in the first part - I was sometimes incorrectly declaring a 8-connected set of obstacle cells to have a bad form, and the bug could only be triggered when such a set wrapped around at least one full cycle in a spiral-like manner. As 8-connected sets of obstacles play no part to the reference solution, it was very hard for the problemsetters to include such testcases into the system test, and thus the solution has actually survived them - but I didn't expect that after seeing it fail the stress testing.

As the challenge phase started, I've learned that all submitted solutions were quite long and hard to check, so challenging seemed hopeless, right until Kankuro challenged qwerty787788's 250-pointer. Now both Kankuro with 265 points and qwerty787788 with 233 points were slightly above my projected result of 225 points, so I've started desperately looking for a challenge. Unfortunately, I couldn't find any flaw in the remaining solutions. The tensions were eased a bit by Kankuro's own 250 failing a challenge from kuniavski, but qwerty787788 still stayed with 233 points until the end of the challenge phase.

After the end of the round, I learned from Egor that the 600 can be solved in a very simple way - I was missing the crucial observation that diagonals are completely independent and can be handled separately, so all the 8-connected-figure complexity was not necessary. I've also learned that qwert787788 had a correct solution, but he only checked it against the example cases and nothing else and thus it was likely to fail. The system test revealed that it did indeed fail, and that my solution unexpectedly passed - but the latter didn't really matter then.

Now I'm deeply regretting the fact that I forgot to turn on the screencast recording before the round started, as it would definitely be valuable to have this experience recorded, so I'm using this blog entry as such recording :)

Thanks a lot to TopCoder, to admins, problemsetters, event planners and organizers, to Jessie, Tim, Makoto and Gaoyuan personally, to the other Algorithm competitors, and to everybody who was watching! See you all at TopCoder Open 2016!

Tuesday, November 10, 2015

TopCoder Open 2015 Finals Finals

TopCoder Open 2015 Onsite Semifinal Round is over (problems, results, top 5 on the left, editorial, my screencast - might still be processing). The round turned out to have a beautiful but very hard 1000-pointer, so (in retrospect) the right strategy was to solve the first two problems, and then make sure the solutions are correct, most probably via stress-testing. However, many competitors including myself and tourist hoped to get the 1000, and thus failed to test the 250 and 500 properly. I was lucky that my solutions still passed (thanks to the wishes for luck in comments!), while tourist unfortunately had his 500 solution fail - very sorry for that, and better luck next year.

The five finalists will have the final battle very soon - the Final Round starts in about 45 minutes. The problem values are 250. 600 and 1000. Wish me some more luck :)

TopCoder Open 2015 Finals

The final round of the 2015 TopCoder Open, the oldest and one of the most prestigious international competitive programming tournaments for individuals, takes place today in Indianapolis (on the left: a small public library inside a city park). There will be two rounds: the Semifinal round, where 12 contestants participate and 5 advance to the finals, from 10:00 TopCoder time to 12:00 TopCoder time (other timezones), and the Final round for those 5, from 15:00 TopCoder time to 17:00 TopCoder time (other timezones).

TopCoder will be doing live coverage on Facebook, and on Twitch (this one is scheduled to start one hour after the beginning of each round, covering the end of coding phase and the challenges).

Wish me luck!

Monday, November 9, 2015

A week with stabilizers

Open Cup 2015-16 Grand Prix of Ekaterinburg took place last week (problems, results, top 5 on the left). Congratulations to the XZ team on their first win of the season! The results were decided by problem H, which asked to count how many different permutations can be generated by a given set of permutations of order at most 15, and thus boiled down to a beautiful but a bit obscure algorithm: the Schreier–Sims algorithm. In my view, the most important result of this round is an elementary description of the Schreier-Sims algorithm by Andrey Halyavin and Maxim Akhmedov (in Russian).

Problem A was the nicest in my opinion. You're given 10000 points on the plane such that no three points lie on the same line. You have to build a triangulation of this set of points, and then answer 100000 requests of the form: which triangle of triangulation covers the point with the given coordinates? You're free to pick any triangulation, so the goal is to pick such one that allows answering these requests quickly.

Thanks for reading, and check back soon for this week's summary!

Thursday, October 29, 2015

An inverse topological week

ACM ICPC 2015 NEERC Moscow Subregional happened on Sunday of the previous week, both onsite as an ACM ICPC round and online for everybody (results, merged results, top 5 on the left). Team Ababahalamaha from the Moscow Institute of Physics and Technology had a standout performance and solved all 12 problems with half an hour to go - amazing!

The most surprising problem in this contest was problem K. You were given a graph, and needed to topologically sort it. And between the possible topological orders, you needed to pick the one where the first vertex is as early as possible, if there are still several choices - the one where the second vertex is as early as possible, and so on.

This problem has two possible approaches. One is somewhat standard, involving advanced data structures and quite tedious to implement. The other one is very simple, but hard to notice. Can you see the latter?

ACM ICPC 2015 SEERC also happened last weekend (problems, results, top 5 on the left, report). While the domination of the Ukrainian teams has become a norm there, the winning team is still somewhat a surprise: Zaporizhzhya National Technical University. Congratulations!

Coming back to last week, TopCoder SRM 672 took place on Wednesday (problems, results, top 5 on the left). Despite failing the hard problem, xudyh has won and continued his meteoric rise through the rankings, and is now the seventh in the world!

ACM ICPC 2015 NEERC Northern, Eastern, and a few other subregionals took place on Saturday using the same problemset (problems, Northern results, merged results, top 5 on the left). The battle between the top Russian teams continued, with yet another team on top this time - congratulations to team Dandelion from the Ural Federal University!

And finally, Codeforces Round 327 wrapped up the competitions on Sunday (problems, results, top 5 on the left). This time it was Endagorion who won despite failing the hardest problem, and continued his climb towards the top of the ranking - way to go!

Last week, I've mentioned a complex dynamic programming problem from a recent TopCoder SRM: consider a grid with 13 rows and 30 columns, with each cell having an arrow pointing either right or down. We go row-by-row starting from the top row, and within each row we go column-by-column starting from the left column, and place dominos (2x1 tiles) on the grid. Whenever we encounter a cell without a domino, we look at its arrow. If it's pointing to the right, and there's an empty cell to the right, we place a domino on those two cells. If it's pointing down and there's an empty cell down, we place a domino on those two cells. If there's no empty cell in the direction of the arrow, we try the other direction (down for right, and right for down). If both directions don't work, we don't place any domino on this cell. Assuming the direction of all arrows is picked uniformly randomly out of all 213*30 possibilities, what's the expected number of placed dominoes at the end of this process?

This type of problem lends itself naturally to a dynamic programming solution. Let's place the dominoes as described in the problem statement. After we've completed a few rows, we can notice that most dominoes we placed don't affect the rest of the placement anymore. More precisely, only the dominoes that stick out to the area that's yet to be processed matter for further computation - see the picture on the left. So we can use dynamic programming where the state is: the number of completely processed rows, the number of cells processed in the first incomplete row, and whether each of the cells directly below the processed ones is empty.

If the grid had 30 rows and 13 columns, we'd have around 30*13*213 states - something we can definitely process in a fraction of a second. However, the grid in this problem had 13 rows and 30 columns instead, and thus the above approach is too slow as it has around 13*30*230 states.

Here's how to speed it up: instead of processing cells in row-major order, let's process them by diagonals as pictured on the left. It's not hard to check that this, in fact, gives exactly the same result in terms of which dominoes are placed where. However, when we process the cells in this order, we have to remember the state of at most 14 cells, and thus the total number of states is around 13*30*214, which is small enough.

Thanks for reading, and check back next week!