Saturday, October 17, 2015

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, M2, M3, ..., and a given amount X, up to 1018. 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!

No comments:

Post a Comment