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!