Edvard's blog

Open Cup Grand Prix of Poland
By Edvard, history, 8 years ago, In Russian

Hello Codeforces!

Lets discuss problems of the Poland contest. Any ideas on A? We came to the problem to count the number of minimal subsets with zero AND. How to count them?

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

»
8 years ago, hide # |
← Rev. 4  
Vote: I like it +5 Vote: I do not like it

Problem A: Let P0[i] = count of numbers i in array. Pk = Pk - 1 × P0, where  ×  is multiplication of polynomials with AND applied to indices instead of sum (like it's described here, I don't know how to correctly name such multiplication). So the task is to find least k such that Pk[0] > 0, and answer will be Pk[0]·k!
It can be done in , where N = 220 , because k is limited by , and we can find Pk[0] in linear time, without inverse transformation.

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

Any simple approach for B? We tried and got TL 52.

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

H ?

→ Reply