spirited_away_'s blog

By spirited_away_, history, 5 years ago, In English

Given a number N, The problem asks you to find all such pairs u,v such that there exists another set of pairs a,b such that

  1. a ^ b = u

  2. a + b = v

where u , v <= N.

I finally concluded that basically we have to find a+b<=N, but how to proceed from here. Can we use counting principle to solve this problem, i mean count all a+b == N and a+b < N and to avoid repeatation we will considere a >= b.

Can anyone tell me the approach and intutition to solve it. Editorial is in japanese.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Apply dynamic programming on digits. First change $$$v$$$ into binary representation and then doing dynamic programming from the most significant bit to the least significant bit, maintaining the last two remaining digits of $$$v-a-b$$$ would be enough. Time complexity is $$$O(\log{N})$$$.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it