Блог пользователя nezametdinov

Hackerrank Vim War problem solution
Автор nezametdinov, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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.

→ Ответить