kazuma_desu's blog

Sum and Xor problem — Codechef
By kazuma_desu, history, 9 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

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

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

hint
→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    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
    • »
      »
      »
      9 years ago, hide # ^ |
      ← 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