Edvard's blog

Open Cup Grand Prix of Poland
By Edvard, history, 7 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

»
7 years ago, # |
← 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
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    We had . We used Mo algo, but to maintain set size we didn't use set, just boolean array and current size

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

      How to achieve with MO? is now feasible with original MO, but not .

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        That was a stupid typo, , ofc

        Sorry for being misleading

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

          Thank you, I was just a bit confused :D

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

H ?

→ Reply