Zlobober's blog

Opencup: Grand Prix of Baltics
By Zlobober, history, 11 years ago, translation, In English

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

  • Vote: I like it
  • +44
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it +49 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you explain in detail, why "conv^-1(conv(clique)^a * conv(antilclique)^b)[full mask] != 0"?

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      "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).

      → Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it +18 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it +13 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      Vote: I like it +10 Vote: I do not like it

      Minor addition to ikatanic answer: last element (in fact, any single element) of conv and conv^-1 can be calculated in O(2^n).

      → Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it +13 Vote: I do not like it

    Could you please give some more details or your code for F.

    → Reply
»
11 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Can some1 describe a solution for C in details more or less?

→ Reply
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

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

→ Reply