### Zlobober's blog

By Zlobober, history, 8 years ago, translation,

Opencup: GP of Baltics has just finished. We are curious, what are the normal solutions for A, B and F?

• +44

 » 8 years ago, # |   +49 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.
•  » » 8 years ago, # ^ |   0 Can you explain in detail, why "conv^-1(conv(clique)^a * conv(antilclique)^b)[full mask] != 0"?
•  » » » 8 years ago, # ^ |   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).
•  » » 8 years ago, # ^ |   +18 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?
•  » » » 8 years ago, # ^ |   +13 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
•  » » » 8 years ago, # ^ |   +10 Minor addition to ikatanic answer: last element (in fact, any single element) of conv and conv^-1 can be calculated in O(2^n).
•  » » 8 years ago, # ^ |   +13 Could you please give some more details or your code for F.
 » 8 years ago, # |   +5 Can some1 describe a solution for C in details more or less?
 » 8 years ago, # | ← Rev. 2 →   +8 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