nezametdinov's blog

Hackerrank Vim War problem solution
By nezametdinov, history, 9 years ago, In English

Statements

Could someone help me with understanding solution to this problem? Although there is an editorial for this problem, there is no explanation or proof of his inclusion-exclusion formula.

This problem's solution keeping me annoying for a long time. Please help me.

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

»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Here is how I understood it -

Number of sets whose OR matches all bits of final number — Number of sets whose OR have exactly 1 bit of the final number unset + Number of sets whose OR has exactly 2 bits of final number unset ...

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

    Yes.

    Number of subsets which bitwise OR is X = number of subsets which bitwise OR is subset of X  -  number of subsets which bitwise OR is subset of X' + number of subsets which OR is X'' and so on.

    X' — X without 1 bit
    X'' — X without 2 bits

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

Consider last line equal to 1111.111. Answer equal to 2n, but you have to subtract the number of subsets such that, first bit equal to 0 for all soldiers in this subset. Then you have to subtract second, third, ...mth. Then you have to add the number of subsets first and second bit equal to 0, and so on. So you can use inclusion - exclusion principle.

→ Reply