CHEFADD - EDITORIAL

[taran_1407]

PROBLEM LINK:

Practice
Contest

Setter: Misha Chorniy
Tester: Hasan Jaddouh
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

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

• Solve the problem in increasing order of bits, handling carry forward carefully.
• Dynamic Programming state consists of tuple (bit, cntA, cntB, carry), where bit is the bit position, cntA is number of bits of A not yet used, cntB is number of bits of B not yet used, and carry tells whether we have one carry forward from the previous position or not.
• Final answer is the value of tuple (0, bit(A), bit(B), carry), where bit(X) counts the number of set bits in X.

EXPLANATION

This 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.

Click to view

Addition of three in Binary

0+0+0 = 00 = 0 value, 0 carry
0+0+1 = 01 = 1 value, 0 carry
0+1+0 = 01 = 1 value, 0 carry
0+1+1 = 10 = 0 value, 1 carry
1+0+0 = 01 = 1 value, 0 carry
1+0+1 = 10 = 0 value, 1 carry
1+1+0 = 10 = 0 value, 1 carry
1+1+1 = 11 = 1 value, 1 carry

This stuff will be useful.

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 bit-by-bit.

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 carry-forward 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 carry-forward 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.

Click to view

You all know Dynamic Programming. You just read what is dynamic programming. In simple words, storing results when calculated once, and reusing them us called Dynamic programming. That’s all. Only thing, which makes Dynamic Programming a scary thing for some people, is identifying, which information to store. This we can learn with practice.

To give a try to a similar DP problem, see this problem, as well as editorial written by me here.

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 Complexity

As 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
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed.

[tarini_1407]

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.

[l_returns]

Again… XD

[aryanc403]

Fun Fact - @l_returns is the first person to comment on this answer.
Mega Fun Fact - @tarini_1407 and @taran_1407 study in same college.
So @taran_1407 you have got one teammate. Search reduced to finding one more. xD

[vijju123]

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

[taran_1407]

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.

[l_returns]

@vijju123 and @aryanc403 XDD

[aryanc403]

lol. Someone using his powers.

Click to view

Click to view

[vijju123]

Thats because it will spam the editorial. 1-2 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.

[vijjji123]

Hi @vijju123,
Please don’t disappoint me and you can convert my answers into a comment on @tarini_1407 answers. Sadly, I don’t have powers to do so.

[aryanc403]

There is no Tarini in my college. lol. You have searched your college database?

[l_returns]

XDDDDDDDDD

[vijju123]

@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.

[tihorsharma123]

Problem in Practice Section is not visible.

[taran_1407]

@ everyone

I just hope next time you all will read my comment carefully. I explicitly mentioned “As far as I know” xD

[pulkitsja]

@taran_1407 : Iterative Solution

[codingalways]

Awesome Editorial just loved it learnt something new

[chari407]

Hey,
For the test case 369 428 797, can you please explain why pairs like (1,796), (2,795) … (795,2) (796,1) valid?
After all, they are obtained by shuffling some bits in A and B. Can you please point out where I am getting confused?
Thanks

[taran_1407]

All of these pairs are not valid.

For verification, write a brute program which iterates over all pairs of (i, c-i) and count the number pairs in which i have same bit count as a and (c-i) has the same bit count as B.

[kunal12]

"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 carry-forward 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 carry-forward 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.