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!