You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFADD - EDITORIAL

3
1

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.

View Content

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.

View Content

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. :)

This question is marked "community wiki".

asked 20 Oct, 07:11

taran_1407's gravatar image

6★taran_1407
3.6k1863
accept rate: 23%

edited 08 Nov, 18:58

admin's gravatar image

0★admin ♦♦
19.6k349497539

Almost similar problem A. XOR Equation.

(29 Oct, 03:38) aryanc4036★

link

answered 21 Oct, 23:37

pulkitsja's gravatar image

4★pulkitsja
162
accept rate: 20%

I couldn't understand your code

(28 Oct, 13:23) vjvjain04★

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. ;)

link

answered 21 Oct, 19:54

tarini_1407's gravatar image

0★tarini_1407
411
accept rate: 0%

Again... XD

(21 Oct, 19:58) l_returns5★

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

(21 Oct, 20:04) aryanc4036★

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, 20:08) vijju123 ♦5★

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, 20:11) taran_14076★
1
(21 Oct, 20:13) l_returns5★

lol. Someone using his powers.

View Content
View Content
(21 Oct, 20:39) aryanc4036★
1

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.

(21 Oct, 20:48) vijju123 ♦5★

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. :(

(21 Oct, 21:09) vijjji1230★

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

(21 Oct, 21:11) aryanc4036★

XDDDDDDDDD

(21 Oct, 21:14) l_returns5★

@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, 21:26) vijju123 ♦5★

@ everyone

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

(21 Oct, 23:24) taran_14076★

Please dont make fun of me or taran!

(27 Oct, 23:38) tarini_14070★
showing 5 of 13 show all

Problem in Practice Section is not visible.

link

answered 21 Oct, 21:57

tihorsharma123's gravatar image

4★tihorsharma123
49718
accept rate: 15%

Awesome Editorial just loved it :) learnt something new

link

answered 22 Oct, 13:47

codingalways's gravatar image

4★codingalways
1
accept rate: 0%

Glad you found it useful.

(24 Oct, 16:37) taran_14076★

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

link

answered 22 Oct, 18:19

chari407's gravatar image

2★chari407
44727
accept rate: 0%

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.

(22 Oct, 20:25) taran_14076★

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

link

answered 23 Oct, 18:14

kunal12's gravatar image

3★kunal12
445
accept rate: 0%

edited 23 Oct, 18:18

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, 16:40) taran_14076★

can you please give one more example explaining this x, cf and y.

(24 Oct, 16:45) kunal123★

Other examples would be similar. I recommend you read and Binary Arithmetic (specifically Binary addition), which you may find by googling.

(24 Oct, 16:54) taran_14076★

tester solution

This solution is showing runtime error(sigtstp) I think its because of declaring such big array. Its having time complexity of O(10^9).

link

answered 24 Oct, 18:03

mohit96m's gravatar image

4★mohit96m
762
accept rate: 16%

What is the brute force approach that would solve one sub task?

link

answered 25 Oct, 22:10

satish1110's gravatar image

3★satish1110
111
accept rate: 0%

@taran_1407 In recursive function, if we add an extra condition bit_a==0 && bit_b==0 return 0; produces WA. Can anyone explain the reason?

link

answered 27 Oct, 23:28

ankush_953's gravatar image

4★ankush_953
356
accept rate: 0%

edited 27 Oct, 23:45

I did not get what you want to say.

(27 Oct, 23:55) taran_14076★

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, 09:23) ankush_9534★
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, 14:32) taran_14076★

@taran_1407 Thanks :)

(31 Oct, 13:35) ankush_9534★

tester program give time limit exceed @admin

link

answered 28 Oct, 20:52

piyush1133's gravatar image

4★piyush1133
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,952
×1,602
×446
×182
×36
×11

question asked: 20 Oct, 07:11

question was seen: 3,669 times

last updated: 08 Nov, 18:58