A week with 13x30

Codeforces Round 325 was the first of two Codeforces rounds this week (problems, results, top 5 on the left). Um_nik has won his second Codeforces round thanks to finishing five problems with more than 30 minutes to go - impressive! Of course, subscriber's bug in problem A has also contributed - better luck next time for him.

TopCoder SRM 671 took place on Wednesday (problems, results, top 5 on the left). The top 5 of the round matched the current top 5 by rating almost exactly - just Burunduk1 did not participate, and snuke has managed to grab the fourth place instead.

I think such high correlation might be due to the fact that the hard problem was an interesting application of advanced dynamic programming, a very "professional" problem. 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?

Had the grid 13 columns and 30 rows, the dynamic programming would be pretty standard. But how do we deal with the transposed grid?

Codeforces Round 326 happened one day later (problems, results, top 5 on the left). With this victory, qwer continued his rocket-like rise through the rankings, with four new "titles" in last four rounds - I'm wondering what comes next :)

Finally, this week had quite a few important ACM ICPC selection rounds. ACM ICPC 2015-16 NEERC Southern subregional (problems, merged results, top 5 on the left, onsite results), together with an online contest on the same problemset three days later, gave us a chance to compare curent ACM ICPC teams where at least some of them were in real competition mode. Moscow State University team Trinity came out on top this time, getting problem M accepted with just 1 minute to go.

Does anybody know if team Excited who placed second is a real ACM ICPC team this year?

ACM ICPC 2015-16 NEERC Moscow subregional and SEERC still haven't published the results, so I'll come back to them next week.

And finally, let's come back to the Running City urban orienteering puzzles I've published in my last post.

The first one was:
1 + 6 = 7
1 + 3 = 2
3 + 6 = 4
4 + 6 = 5
Find a house with bas-relief sculptures at the northern end of the 4th. How many bas-reliefs with sheafs are there on the street facade?

The number referred to colors of the rainbow, and addition stood for mixing two paint colors: red + indigo = violet, and so on. "The 4th" referred to the Green street, or улица Зелёная.

The second one was:
The older brother got a highway, a street, and an alley (albeit an old-fashioned one). The middle sister got an avenue and a street, not too bad as well. The younger brother, however, got just one little alley. Find house number 6 on the younger brother's alley, and count the number of mosaics on the facade.

Here, the answer was the capitals of the Baltic states: there are Tallinn highway, Tallinn street, Reval (the old name of Tallinn) alley, Riga avenue, Riga street and Vilnius alley in St. Petersburg. When solving this puzzle, our team employed programming: we've parsed a list of all streets of St. Petersburg, and found the intersection of the highway and street names which turned out to be surprisingly small, then looked at them one by one until Tallinn "clicked".

Thanks for reading, and check back next week!