kazuma_desu's blog

Sum and Xor problem — Codechef
By kazuma_desu, history, 7 years ago, In English

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!

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

»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

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

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

      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.

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

        But there is still more to the problem. Please read it again.

        → Reply