PROBLEM LINK:Setter: Misha Chorniy DIFFICULTY:EasyMedium PREREQUISITES:Bitwise operation, Dynammic Programming. PROBLEM:Given three numbers $A$, $B$ and $C$, given $A+B = C$, We can change positions of bits in $A$ as well as in $B$. Calculate Number of ways we can do so, such that their sum is $C$. SUPER QUICK EXPLANATION
EXPLANATIONThis solution seems complicated implementation at first sight, but is actually not, if you are comfortable with Bitwise Operations. First of all, I am going to share very basic stuff about bitwise addition in secret box. Now, we all know, that we $A+B$ should have all bits same as $C$. We need to count the number of ways to shuffle bits. So, we are going to handle problem bitbybit. Important thing is, that If we add two bits at a position, there may be a carry forward to next bit. This means, that bit to be chosen at the next significant position is dependent on carryforward from the previous position. This means, that we have to approach the bits from least significant bit to most significant bit. So, Suppose we need to have a bit at current position to be $x$, with carryforward $cf$ from the previous position. If $x$ is same as $cf$, We can either have the current bit set in both numbers or none of them. Because if we choose to have set bit in exactly $A$ or $B$ at the current bit, the current bit will get flipped, resulting in $A+B \neq C$. If $x$ is not same as $y$, we have to flip the current bit, which can be done only if exactly one of the $A$ or $B$ have current bit set, which will lead to flipping the current bit. If you have understood this much, give it a try. After doing this much, If you build a simple recursive solution, we would probably get Time Limit Exceeded, since our solution is calculating some values multiple times, resulting in exponential time complexity. To speed up, you can just notice, that you can build a lookup table ans[bit][cntA][cntB][carry], storing answer for the tuple (bit, cntA, cntB, carry) and instead of calculating it, just look it up from here. This result in reducing time complexity from exponential to polynomial time complexity, sufficiently fast to pass time limit. A secret box, only for people who do not know Dynamic Programming. Editorialist's talk I was going through some accepted codes for this problem when I found this really nice solution. Have a look. I was looking for an iterative solution to this problem. Anyone having completely iterative solution will be mentioned here. Please share with me the link of code. EDIT: A completely iterative solution can be seen here, by @pulkit_sja Time ComplexityAs you will commonly find in dynamic programming problems, Actual time complexity depends upon Number of states visited. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 20 Oct '18, 07:11

answered 21 Oct '18, 23:37

Thank you for your highly insightful editorials! I remembered your editorials from ICO prep round and previous contests which helped me improve my dp. Because of it I was able to solve this question. Please keep posting these lovely editorials. ;) answered 21 Oct '18, 19:54
Again... XD
(21 Oct '18, 19:58)
Fun Fact  @l_returns is the first person to comment on this answer.
(21 Oct '18, 20:04)
Fun fact 3  This statement is worth reading. https://www.codechef.com/ICOP1902/problems/TARITAR I guess @taran_1407 has a huge female fan following in his college
(21 Oct '18, 20:08)
I expect one of my friends is pulling this prank on me. As far as I know, There is no Tarini in my college. So, teammate search continues.
(21 Oct '18, 20:11)
lol. Someone using his powers.
(21 Oct '18, 20:39)
1
Thats because it will spam the editorial. 12 jokes are fine but that answer simply opens up a new road to spam more and more XD. I dont have issues of it using my name, but the fact that it will spam the editorial unnecessarily  I consulted taran also before removing it.
(21 Oct '18, 20:48)
Hi @vijju123,
(21 Oct '18, 21:09)
(21 Oct '18, 21:11)
XDDDDDDDDD
(21 Oct '18, 21:14)
@aryanc403  @taran_1407 knows everything about girls in his college, as evident from his statement ;) @vijjji123  Sadly there, there is only disappointment from me in your fate. I wont be writing editorials for a long, long time XD.
(21 Oct '18, 21:26)
@ everyone I just hope next time you all will read my comment carefully. I explicitly mentioned "As far as I know" xD
(21 Oct '18, 23:24)
Please dont make fun of me or taran!
(27 Oct '18, 23:38)
showing 5 of 13
show all

Problem in Practice Section is not visible. answered 21 Oct '18, 21:57

Awesome Editorial just loved it :) learnt something new answered 22 Oct '18, 13:47

"Important thing is, that If we add two bits at a position, there may be a carry forward to next bit. This means, that bit to be chosen at the next significant position is dependent on carryforward from the previous position. This means, that we have to approach the bits from least significant bit to most significant bit. So, Suppose we need to have a bit at current position to be x, with carryforward cf from the previous position. If x is same as cf, We can either have the current bit set in both numbers or none of them. Because if we choose to have set bit in exactly A or B at the current bit, the current bit will get flipped, resulting in A+B≠C. If x is not same as y, we have to flip the current bit, which can be done only if exactly one of the A or B have current bit set, which will lead to flipping the current bit." @taran_1407 @vijju123 can you please explain these bunch of statements with an example. answered 23 Oct '18, 18:14
Add two numbers in binary form. 1010 0110 you'll see, that sum is 10000. This happened due to carry forward at bit index 1, 2 and 3 (counting from least significant to most significant). Analyse this example and you'll get it.
(24 Oct '18, 16:40)
can you please give one more example explaining this x, cf and y.
(24 Oct '18, 16:45)
Other examples would be similar. I recommend you read and Binary Arithmetic (specifically Binary addition), which you may find by googling.
(24 Oct '18, 16:54)

This solution is showing runtime error(sigtstp) I think its because of declaring such big array. Its having time complexity of O(10^9). answered 24 Oct '18, 18:03

What is the brute force approach that would solve one sub task? answered 25 Oct '18, 22:10

@taran_1407 In recursive function, if we add an extra condition answered 27 Oct '18, 23:28
I did not get what you want to say.
(27 Oct '18, 23:55)
In your solution, if we add an extra condition in recursive function ans a == 0&& b== 0 return 0 gives WA. Why ? and why do we need to add condition bit==B ??
(28 Oct '18, 09:23)
1
Because cf may be balancing the remaining bits as required for c. Like, suppose we have a==0 && b==0. we need the current bit to be 1, and cf is also 1. Hence, This bit we get from cf. Assuming all next bits are 0, we have one way which, due to that condition, will be missed.
(28 Oct '18, 14:32)
@taran_1407 Thanks :)
(31 Oct '18, 13:35)

Almost similar problem A. XOR Equation.