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 2^13*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*2¹³ 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*2³⁰ 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*2¹⁴, which is small enough.

Thanks for reading, and check back next week!

Tweet