EOOPR - Editorial

Problem : The One Who Knocks!

Setter: Aman Singhal

Tester: Yashodhan Agnihotri

Editorialist: Aman Singhal

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Programming, Ad-hoc

PROBLEM:

You are given two values X and Y. You have to choose one positive odd integer ‘a’ and one positive even integer ‘b’. In one operation you can either add a to X or subtract b from X. You cannot change a and b once you start performing operations. You have to find the minimum number of operations to obtain Y from X.

QUICK EXPLANATION:

  • When X>Y, it will take 1 operation if the difference is even, else 2.
  • When X<Y, it will take 1 operation when difference is odd, 2 when difference is even but not divisible by 4 else 3.
  • When X=Y, it will take 0 operation.

EXPLANATION:

There are 3 cases to be solved in this question:

Case 1: When X>Y

Tap to view
  • In this case we have to decrease the value of X. We can only subtract the even value. So, if the difference is even then in one round we can reach Y .
              X-b=Y
  • Now for odd differences, the observation here is that the difference of an even and odd number is always odd. So we can add any odd number and now subtract the difference as it will be an even number.
              X+a-b=Y

Case 2: When X<Y

Tap to view
  • In this case we have to increase the value of X. We can add the odd value. So, if our difference is odd then in one round we can reach Y.
              X+a= Y

  • When our difference is even then we have to perform at least two operations. We can add the odd number twice as the sum of two odd numbers will give an even number but this even number will not be divisible by 4. In such cases where our difference is even and not divisible by 4 it will take 2 operations.
              X+a+a = Y

  • Now our last case, when we have difference as even and divisible by 4, we can achieve Y by adding two odd numbers giving sum greater than difference and then subtract the even number in order to achieve Y. In this case it will take 3 operations.
              X+a+a-b = Y

Case 3: When X=Y

Tap to view
  • In this case we don’t need to perform any operation.
              X=Y

TIME COMPLEXITY:

  • Time complexity per test case is O(1).

SOLUTIONS

Setter’s Solution (Python 3)
T=int(input())
for _ in range(T):
    X,Y=map(int,input().split())
    diff=abs(X-Y)
    if(X>Y):
        if (diff%2==0):
            ans=1
        else:
            ans=2
            
    elif (X<Y):
        if (diff%2!=0):
            ans=1

        elif (diff%4==0):
            ans=3

        else:
            ans=2

    else:
        ans=0

    print(ans)


Tester’s Solution (C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define zapp ios::sync_with_stdio(false);cin.tie(0)
 
int main()
{
	zapp;
	ll t;
	cin >> t;
	while (t--)
	{
		ll x, y;
		cin >> x >> y;
		ll moves = 0;
		if (x > y) {
			ll diff = x - y;
			if (diff % 2 == 0)
				moves = 1;
			else
				moves = 2;
		}
		else if (x < y) {
			ll diff = y - x;
			if (diff % 2)
				moves = 1;
			else if (diff % 2 == 0 && (diff / 2) % 2)
				moves = 2;
			else
				moves = 3;
		}
		cout << moves << "\n";
	}
	return 0;
} 

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed.

9 Likes

in X < Y
let X=2 and Y=10
difference is 8 and thus divisible by 4
but we can achieve 10 from 2 by 2+9-1 which takes minimum 2 operations…is this wrong?

1 Like

Yes this is wrong,
2+9 is correct but you cant subtract an odd number.
You have to subtract an even number.

1 Like

and what about 2+7+1?

To achieve 10 from 2 ,
a=5 b=2
we can do, 2+a+a-b = 10

1 Like

you can’t change a or b more than once.

2 Likes

oh! i get it now.

1 Like

You can refer this explaination - Click Here

ohh sorry My Bad I got it now

1 Like

for testcase x>y ans is should be ans=0 right ?
eg
x=4 y=0;
means he has already achieved y at certain point of time and now current level of cleaning is x=4
so what i mean is does he has to reduce level of cleaning to achieved y ? @aman1108

1 Like

how can this problem as real world problem. why any one wants to reduce his work
to achieved something which he already done.

Can anyone please tell me some examples of 3 moves please??

1 Like

x=1 y=7
first we add 7 to x hence it becomes 8 now.then we subtract 8 from x now x becomes 0 and then again we add 7 to x which becomes 7. so a=7 and b=8.

When X<Y it will take 1 operation when difference is odd, 2 when difference is even but not divisible by 4 else 3,
cananyone explain this?

1 Like

x=4 y=0 , means that in how many minimum steps you would take to go from 4 (x) to 0 (y).

1 Like

You can refer this - Click here

1 Like

Thanks bro

1 Like

Refer this for explaination and example - Click Here

but bro why it can not be happened he has already cleaned his lab and now he is at x=4
which is current .
what i mean he is already done minimum steps to achieved y

1 Like

No we are not assuming that its already done.
Problem is to go from x to y in minimum steps.

1 Like