MAKEQUAL Editorial

[foxy7]

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

2060

PREREQUISITES:

Bitwise Operations

PROBLEM:

You are given 3 numbers A, B and C.

You want to make all these 3 numbers equal. To do this, you can perform any finite number of operations:

• In the i^{th} operation, you must add 2^{(i-1)} to any one of these 3 numbers.

Find whether you can make these 3 numbers equal in finite number of moves.

EXPLANATION:

Here in each operation we are adding a set bit as we move along from right to left. When we are on the i_{th} operation, i.e adding the i_{th} set bit, we look for all possibilities:

• In case all three numbers are already equal, we can end the operation and conclude that it is possible to make all three numbers equal.
• Else if any two of them have a set bit, we can simply add set bit to the number having the unset bit at i_{th} position, this way all three numbers will have same bit at the i_{th} position and we can move to the next bit position.
• Else if any two of them have unset bit, then we can add set bit to the number having the set bit at i_{th} position, to make it unset at that position. This way all three numbers will have unset bit at the i_{th} position and we can move to the next bit position.
• In any other case, i.e case when we have no set bits or all set bits, there is no way we can make all three numbers to have same bit at the i_{th} position so it won’t be possible to make the three numbers equal.

TIME COMPLEXITY:

O(log(N)), for each test case.

SOLUTION:

Editorialist’s Solution
Tester1’s Solution
Tester2’s Solution

[xaier310]

Can someone tell me for which test case my code is not working
https://www.codechef.com/viewsolution/66964288

[akshatanand186]

Test Case

4 6 7

Soln is 7+1 = 8, 6 + 2 = 8, 4 + 4 = 8

[paperba1l]

what is wrong in my solution - CodeChef: Practical coding for everyone

is did not understand why we are breaking when cont of set bits is either zero or three. Can someone please explain?

[darklord99]

We MUST add 2^(i-1) at every step. If all the set bits is zero, then adding 2^(i-1) to a or b or c will result in one of the set bits to become 1. Hence the nos. can never be equal after the further steps.
Similarly, if all 3 of them are 1, then doing this operation will convert one of the bits to 0 as adding 2^(i-1) will shift all the bits towards right by 1(in the binary format), starting from this position. Therefore, you cannot make the nos. equal afterwards.

[l_cube]

Continuing the discussion from MAKEQUAL Editorial:

hey guys,
i tried to solve it using simple maths, don’t know where is it getting wrong
let the three number is a, b, c and final number is x

• x-a + x-b + x-c = 2^0 + 2^1…2^k;

• 3*x-(a+b+c) = 2^m - 1

• 3*x = (2^m + (a+b+c-1))

so turns out RHS should be multiple of 3, to get x, but solving this was giving wrong ans.

[paperba1l]

damn, misunderstood an easy question. was this close to solving question.
my bad. thanks

[rhymehatch]

Yeah, sum should be a multiple of 3 but it does not help you.

For example, numbers 1 2 6 will immediately sum to a multiple of 3, you will get x = 3 but you cannot reach 3 from 6. Then you will need to make sure x >= \text{max}(a,b,c), but you still need to figure out if you can reach x with additions to other numbers.

[codurr]

After ensuring that RHS is divisible by 3 and that x > max(a, b, c) you can check for all such x if you can make a,b and c equal. Solution

[disasteroid]

First, if A = B = C, the answer is YES.

Let after i operations,
X is added to A,
Y is added to B,
Z is added to C,
P = X+Y+Z,
and S = A + B + C + X + Y + Z.

Clearly, X+Y+Z = 1 + 2^1 + 2^2 + … + 2^(i-1) = 2^i - 1
So,P = 2^i - 1 and S = A + B + C + P

Now, if they were to be equal after i operations, the following equation must hold:
A + X = B + Y = C + Z = S/3

So, S should be a multiple of 3. If S is not a multiple of 3 , then A, B , and C cannot be equal after i operations.

X = S/3 - A
Y = S/3 - B
Z = S/3 - C

Also, X, Y and Z should be non-negative and must have unique set bit positions because each power of 2 can only be added to one of the numbers A , B and C so that position can be set in only one of the numbers X, Y ad Z.
This can be checked by taking the bitwise XOR of X , Y and Z which will be equal to P.

so if the following two conditions hold, A , B and C will become equal after i operations:

1. X >= 0 && Y >= 0 && Z >= 0
2. X ^ Y ^ Z = P ( ^ is bitwise XOR)

We can check for log(N) operations, if it can be achieved otherwise the answer will be simply NO.

[bug_found]

Can someone tell me why is my solution giving WA only on test case 2

https://www.codechef.com/viewsolution/66956216

[anon50026379]

In the editorialist’s Solution , why the for loop ( line no. 11) is running from [0,40).

[jazzhacker]

5 40 51 will fail in your code

All these 3 numbers can become 53.
5 + (16) + (32) = 53
40 + (1) + (4) + (8) = 53
51 + (2) = 53

Hope this helps!

[jazzhacker]

I am trying to understand what did I do wrong. Can anyone let me know which case am I missing?
Here is the link to my solution: CodeChef: Practical coding for everyone

Attaching the SubTask Info, the Task #2 was giving WA.

[shubhamjr]

The max value of the numbers can be 10^9 .
and, you have to loop through all the bits of that number.

So, the max no. of bits can be = ( log 10^9 base 2 ) = 9 * ( log 10 base 2 ) = 9 * 3.32,
which is 29.88, means 30 .

So, we have to run the loop from [ 0 , 30 ]

[judaybhasker03]

even i am having the same problem with test case 2 , if you found out the reason can you please post it here.

[hasan_1617]

I’m not getting where I’m wrong can anyone help.
3x = A+B+C+(2^m - 1)
we can see that the reminder of 2^m - 1 will be 1 or 0 1%3 = 1,3%3=0,7%3=1,15%3=0,…so on.
So if the reminder of sum of 3 number is 0 or 2 there must be a possible solution say 1 2 6 here reminder is 0 so any number having reminder 0 and equal to 2^m -1 for a valid m and greater than max(A,B,C) will give the solution say 15 or 63 anything that doesn’t matter but there will be always a solution because alternate reminders 1 and 0 will come.