Opencup: GP of Baltics has just finished. We are curious, what are the normal solutions for A, B and F?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
F: Dynamic programming d[mask] = (minimal number of subsets one can split mask into, minimal sum in the last subset).
A: Define convolution conv(d)[mask] = sum {d[x] | x is submask of mask}. One can calculate conv and conv^-1 in O(n2^n). Let clique[mask] = 1 if mask is clique, 0 otherwise. One need to check conv^-1(conv(clique)^a * conv(antilclique)^b)[full mask] != 0 -- then one can split graph in no more than a cliques and b anticliques. This can be done in O(n2^n) overall.
Can you explain in detail, why "conv^-1(conv(clique)^a * conv(antilclique)^b)[full mask] != 0"?
"conv^-1(conv(clique)^a * conv(antilclique)^b)[full mask]" is a number of ways to choose (not necessarily distinct, possible intersecting) a cliques and b anticliques covering entire graph (i.e. all vertices).
For the fixed a and b, I can calculate conv^-1(conv(clique)^a * conv(antilclique)^b) in O(n2^n) easily. But how to make it O(n2^n) overall?
You can use two properties of the problem to speed it up: 1. in a row (or a column) ones will form an interval 2. you only need last element of conv^-1(...), not the entire result
Minor addition to ikatanic answer: last element (in fact, any single element) of conv and conv^-1 can be calculated in O(2^n).
Could you please give some more details or your code for F.
Can some1 describe a solution for C in details more or less?
Is it possible to see solutions or editorial of this contest ?
If yes, please share link.
I want to see solution of 'F'. problem link is here. Thanks in advance