TCOMPUTE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author, Tester & Editorialist: Devanshu Garg

DIFFICULTY:

EASY - MEDIUM

PREREQUISITES:

Greedy, DP, Math

PROBLEM:

Task was to write a program that takes two non - negative integers X and Y as an input and output a single non - negative integer Z, which is equivalent to X' * Y'.
X' and Y' satisfy the following two conditions:

  • X = X' + Y',
  • Y = X' \oplus Y', where \oplus is bit-wise exclusive or.

Since Z can be large, output Z modulo 1000000007 (10^9 + 7).

Note - X' is the smallest number among all the numbers which satisfy the above two conditions.

EXPLANATION:

Let’s take a look at some bit in X^{'}, which is equal to 1. If the respective bit in Y^{'} is equal to 0, then we can swap these two bits, thus reducing X^{'} and increasing Y^{'} without changing their sum and xor. We can conclude that if some bit in X^{'} is equal to 1 then the respective bit in Y^{'} is also equal to 1. Thus, Y^{'} = X^{'} + Y. Taking into account that X^{'} + Y^{'} = X^{'} + X^{'} + Y = X, we can obtain the following formulas for finding X^{'} and Y^{'}:

  • X^{'} = (X - Y) / 2
  • Y^{'} = X^{'} + Y

One should also notice that if X < Y or X and Y have different parity, then the answer doesn’t exist and we should output -1. If X^{'} and (X - X^{'}) \neq X^{'} then the answer is also -1.

Now if we have computed X^{'} and Y^{'}, then we just need to multiply them to get the desired value of Z.

SOLUTIONS:

Editorialist's Solution 
x, y = map(int, input().split())
if (x + y) & 1:
    print(-1)
else:
    mod = int(1e9+7)
    x_ = (x - y) // 2
    y_ = x_ + y
    print(((x_ % mod) * y_) % mod)

Well this was my approach, feel free to share your approach here. Suggestions are always welcomed.

1 Like
2

can you explain Y’ = X’ + Y with some example ?

3

Although the 2nd problem has also a good one but observation was easy .But this one really good one specially for beginner like me. but how did medium level coder came up with this lot of observation like Y’=X’+Y and *X and Y should have different parity *. did this type of problem came from some generic version problem or just ad-hoc one or observation based.

4

why X and Y should have different parity although I got Y’=X’+Y part .can you reply on that ? Thanks in Advanced for reply.

5

no reply till no. :worried:

1 Like
6

The given solution to the problem is derived as:

Notice in the problem statement that we need to minimise the value of X'.

Let’s suppose we are given X = 17 and Y = 13 i.e., X' + Y' = 17 and X' \oplus Y' = 13.

We are aware about the property of sum and xor that they are commutative i.e., if we swap the set bits of X' with corresponding unset bits of Y', we can minimise the value of X' without changing the value of their sum and xor.

For instance, take X' = 7 and Y' = 10, satisfying the sum and xor condition.

Now, X' = 0111 and Y' = 1010.
After swapping the bits, we get, X' = 0010 = 2 and Y' = 1111 = 15.

As we can clearly see that, X' + Y' = 2 + 15 = 17 and X' \oplus Y' = 2 \oplus 15 = 13.

Now we know that,

X' + Y' = X and Y'= Y \oplus X' = Y + X', using these we can easily derive the formula,

X' = (X - Y) / 2

Similarly, now Y' can easily be computed using any formula, Y'= X' \oplus Y , Y'= X' + Y .

Now consider X and Y have different parity i.e., either X is odd, Y is even or X is even, Y is odd. In both these cases if you try to compute the value of X', you will get (X - Y) as odd so you won’t get the correct value of X' as on computing (X - Y)/2 will give decimal value.

Thus, for solution to exist X and Y should have same parity i.e., either both should be odd or both should be even.

I hope you will find it useful and hope this clears your doubt as well. Sorry for the delay in response.

1 Like