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!

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!

A week with sheafs

The biggest contest of last week for me was not a programming one: Running City 2015 took place in Saint Petersburg on Saturday (Bronevik-pro category: problems in Russian, results in Russian, top 5 on the left, all categories: problems in Russian, winners in Russian). This is an urban orienteering contest, where teams compete against one another to visit as many control points in the city as possible as fast as possible. However, it's not just about running, commuting or driving: first, the organizers try to pick interesting control points, so that you see interesting places and learn a lot about the city, so it's also a sightseeing tour in a sense. More importantly (at least for me), some control points are not simply given to you on the map or as a street adress; instead, they are given to you as puzzles. Only after solving the puzzle you know where you should go.

The puzzles are in Russian and often involve play on Russian words and/or Russian cultural context, but here's one from this year's contest that's somewhat international:

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?

Here "4th" refers to a street, but not literally called "4th", but rather referring to "4" in the equations above. Counting bas-reliefs with sheafs serves two purposes: first, it's a good way to prove that you've actually found the right spot in the city that doesn't require a judge to always be there, and second, it helps you verify that your solution to the puzzle is correct - if there are no bas-reliefs with sheafs in the place you come to, you need to think again :)

Here's another puzzle from this year's contest, which requires more local knowledge, but at the same time is more typical for the contest as it requires to match one's ideas with the actual city streets:

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.

The competition has a lot of categories, differing in difficulty (some require just 4-5 hours, some 10+), allowed means of transportation (only walking, walking and running, public transportation, no restrictions which effectively means driving), and the style of control points (given as an address, or as a puzzle). I'm usually participating in the difficult no-transportation-restrictions all-control-points-as-puzzles category, called "Bronevik-pro", but I think it's great that they provide categories to everybody's taste - i.e., I can totally understand how many competitors find it exciting to look for ways to find creative ways of using public transportation and the best order of passing control points in the "Atlant" category.

Most of their competitions happen in Russia, but they do have some international presense (planned for 2016: Helsinki, Milan, Istanbul), and to the best of my knowledge the international competitions have some categories in English, so if you notice your city on the event list, I think it's worth participating in :)

TopCoder SRM 670 took place during the Running City (problems, results, top 5 on the left). In addition to the highest score from coding, tourist has managed to gain +150 from challenges, although it turned out to be not even necessary for this vey convincing victory - great job!

Sunday was the day for Open Cup 2014-15 Grand Prix of SPb (results, top 5 on the left), The Nizhny Novgorod SU team has won their second Grand Prix of the season, matching Past Glory's achievements - way to go!

This round had many nice problems, but let me mention the most difficult one, problem C. Consider an undirected graph without repeated edges (but possibly with loops) with n vertices. Such graph is called Eulerian if and only if there's a cycle that traverses each edge exactly once. How many Eulerian graphs with n vertices exist, up to isomorphism? n is up to 60, you need to output the answer modulo 10⁹+7.

Last week, I've mentioned an old problem that I couldn't understand my own solution for. The problem was: given an amount, and a set of coin denominations such that for every two denominations one divides the other evenly, how many ways are there to assemble the given amount?

After some time, I think I've figured my solution out :) Let's create a graph interpretation for our problem. We'll create a directed graph with n "layers", each layer corresponding to one coin denomination. For a layer corresponding to denomination x, there are vertices corresponding to amounts 0, x, 2x, ... For each vertex there's an arc to the next highest amount in the same layer. Additionally, for each vertex except those on the first layer there's an arc to the same amount on the previous layer - the one corresponding to the next smallest denomination. The picture on the left illustrates the graph corresponding to denominations 1, 2, 4 and 12.

We can notice now that the ways to assemble the required amount a correspond to the ways to go from vertex 0 on the n-th layer to vertex a on the first layer: every time we make a horizontal move inside the layer corresponding to denomination x, we take one coin of denomination x. Because we're only allowed to move horizontally or upwards, we will enumerate the coins in non-increasing order, and thus each way to assemble the required amount will be counted exactly once.

Now we'll use dynamic programming to find the number of ways to reach amount p on layer q. To transition from amount p to amount p+1, we need to consider horizontal movement, which doesn't change the layer, and also upwards movement, which means we should add the number of ways to reach layer q to the number of ways to reach each smaller layer, assuming layer q has a vertex at the amount p+1. If we write all answers for one p as a vector, transitioning from p to p+1 corresponds to multiplying this vector by a matrix, and there are n different matrices in play, depending on the highest denomination that divides p+1. Finally, fast matrix exponentiation allows us to multiply those matrices fast enough.

Hopefully the code (requires TopCoder login) makes more sense now:
public int solve(long coins_sum, long[] values) {
    int n = values.length;
    long[][][] oneCycle = new long[n][][];
    oneCycle[0] = unitMatrix(n);
    for (int i = 1; i < n; ++i) {
        long curBy = values[i] / values[i - 1];
        oneCycle[i] = multiply(extraMatrix(n, i), pow(oneCycle[i - 1], curBy));
    }
    long[][] total = unitMatrix(n);
    for (int i = n - 1; i >= 0; --i) {
        long fullCycles = coins_sum / values[i];
        coins_sum %= values[i];
        total = multiply(pow(oneCycle[i], fullCycles), total);
    }
    long res = 0;
    for (long x : total[0])
        res += x;
    return (int) (res % MODULO);
}

private long[][] extraMatrix(int n, int start) {
    long[][] res = unitMatrix(n);
    for (int i = 0; i < start; ++i)
        res[i][start] = 1;
    return res;
}

Thanks for reading, and check back tomorrow for this week's summary and for answers to the Running City puzzles!

A week with old self

// This post is for Sep 28 - Oct 4 week. I'm sorry for the delay!

Monday was the day of TopCoder SRM 669 (problems, results, top 5 on the left, Egor's screencast). It would seem that Egor has found renewed motivation in my publishing of his screencasts in this blog: two weeks ago he jumped onto the leaving TopCoder Open train during the challenge phase, and this time he won the SRM easily - great job!

The most interesting aspect of this match for me was about the hard problem. You're given an infinite amount of coins of each denomination from 1, M, M², M³, ..., and a given amount X, up to 10¹⁸. M is up to 1000. How many ways are there to assemble this amount using the given coin types?

I didn't have much time left for this problem, but I also didn't have any good ideas how to approach it. After the match has ended, we've found out that a more difficult version of this problem has appeared in SRM 527 four years ago: in that problem, the denominations were not fixed to powers of a single integer, and the only constraint was that for every two denominations one divided the other evenly. Back in 2011, both I and Egor have solved the problem, but neither I nor him remembered anything about it :)

That's when things started to be a little surreal. I've opened my solution (requires TopCoder login) from that match - and I couldn't understand how it worked! After some time and effort, I've finally figured it out, and I'll tell more in the next week's summary - but in the meantime, can you understand it? Here's the main part of the code:

public int solve(long coins_sum, long[] values) {
    int n = values.length;
    long[][][] oneCycle = new long[n][][];
    oneCycle[0] = unitMatrix(n);
    for (int i = 1; i < n; ++i) {
        long curBy = values[i] / values[i - 1];
        oneCycle[i] = multiply(extraMatrix(n, i), pow(oneCycle[i - 1], curBy));
    }
    long[][] total = unitMatrix(n);
    for (int i = n - 1; i >= 0; --i) {
        long fullCycles = coins_sum / values[i];
        coins_sum %= values[i];
        total = multiply(pow(oneCycle[i], fullCycles), total);
    }
    long res = 0;
    for (long x : total[0])
        res += x;
    return (int) (res % MODULO);
}

private long[][] extraMatrix(int n, int start) {
    long[][] res = unitMatrix(n);
    for (int i = 0; i < start; ++i)
        res[i][start] = 1;
    return res;
}

Codeforces Round 323 took place on Saturday (problems, results, top 5 on the left). Ecnerwal has continued his great form that helped him qualify for the TopCoder Open, and won this round, but both ikatanic and uwi finished extremely close, within 7 points of the first place - congratulations to all three!

And finally, Open Cup 2015-16 Round 3, the Grand Prix of Eurasia, happened on Sunday (problems, results, top 5 on the left). The problemset was mostly easy, but still team Past Glory has achieved an amazing feat, solving the first 10 problems in just 1 hour and 23 minutes! Of course, winning the round after that was almost guaranteed. Congratulations!

Thanks for reading, and check back tomorrow for last week's summary!

A week with a Japanese surprise

The Open Cup held a surprise second round, the Grand Prix of Japan, last Sunday (results, top 5 on the left, overall standings). Past Glory team returned to, well, past glory with a very convincing victory - congratulations!

Problem B, while not very difficult algorithmically, presented a nice implementation challenge: one could write the code in 10 minutes, but could also spend an hour or more. You were given 3000 boosters with integer coordinates up to 10⁹, each pointing in one of four cardinal directions. You can start at any booster, fly in the direction in points to the next booster (if any), then fly in the direction that booster points, and so on. As soon as you leave a booster, it disappears, so you don't change your direction when you pass through its point again. What is the maximum number of boosters you can visit if you choose your starting booster properly?

In my previous post, I've mentioned the medium problem from TCO 2015 Round 3B: you are given 200000 cookies (3 types pictured on the left), with two players taking those cookies in turn one by one. Each cookie has some value for the first player, and some possibly different value for the second player. It is known that the second player always takes the cookie with highest value for him, and when there are several, with the highest value for the first player among those. The first player, on the other hand, is more flexible. He can take any cookie, and his goal is to maximize the total value of the cookies he gets in the end to him minus the total value of the cookies the second player gets in the end to the second player. What is the optimal strategy for the first player?

I won't tell you the full solution, but I will give you a key hint. Let's forget about the goal of the first player, and simply ask ourselves: which subsets of cookies can he achieve? Let's also order the cookies by second player's priorities: first by decreasing value for the second player, then by decreasing value for the first player. It's clear now that the second player will take either the first or the second cookie in this order on the first move, one of the first four cookies on the second move, and so on. In fact, the first player can achieve any subset that has the following properties: at most one cookie from the first two, at most two cookies from the first four, at most three cookies from the first six, and so on.

This is not the full solution yet, but we've effectively removed the game from the problem - now we just have a question about some subsets of our set, and this question is much easier to answer.

Thanks for reading, and check back next week!