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

Sum and Xor problem — Codechef
Автор kazuma_desu, история, 7 лет назад, По-английски

Can someone share their ideas on the following problem?

https://www.codechef.com/problems/CHN16H

The problem is from ACM-ICPC 2016 Chennai Onsite Round.

Thanks!

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

»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

627A - XOR Equation same problem in CodeForces.com !

hint
→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually, the problem deals with triplets instead of pairs so I am not sure if the idea can be extended here.

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

      Well my solution can easily be extended. The idea is to use DP on the binary representation. And the state is:

      dp[current bit][carry in sum] = triples of binary numbers of length [current bit] with given carry in the previous addition.

      → Ответить