// 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;
}
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;
}
Thanks for reading, and check back tomorrow for last week's summary!
0 komentar:
Post a Comment