### spirited_away_'s blog

By spirited_away_, history, 18 months ago,

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.

• 0

 » 18 months ago, # |   0 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})$.
•  » » 18 months ago, # ^ |   0 Hello, But what would be the transition. by moving from i to i-1, what changes should be make in our dp states.
•  » » » 17 months ago, # ^ |   0 ??
•  » » 11 months ago, # ^ |   0 I'm sorry, but i'm not able to understand your explanation clearly. Could you please explain more in detail?TIA
 » 11 months ago, # |   0 http://codeforces.com/blog/entry/71647#comment-559893Hope it helps a bit.