INCREAR-Editorial

editorial
, ,
1

PROBLEM LINK:

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

Setter: Soumyadeep Pal
Tester: Abhinav Sharma, Lavish Gupta
Editorialist: Devendra Singh

DIFFICULTY:

852

PREREQUISITES:

None

PROBLEM:

Chef has two integers X and Y. Chef wants to perform some operations to make X and Y equal. In one operation, Chef can either:

  • set X := X + 1
  • or set Y := Y + 2

Find the minimum number of operations required to make X and Y equal.

EXPLANATION:

There are two cases:
Case 1 X\leq Y: Since, Y cannot be decreased by any method, therefore X has to be increased by at least Y-X. Thus, this is the minimum number of operations and all operations are of type 1.
Case 2 X>Y: Y has to be made at least X. Therefore the minimum number of operations is ceil(\frac{(Y-X)}{2}). If X and Y don’t have the same parity then Y would be increased to X+1 by doing these operations and thus we need to do one more operation which is increasing X by 1.
\therefore answer = ((X\leq Y)?Y-X:\frac{(X-Y+1)}{2}+1- (X%2==Y%2))

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Setter's solution 
#include<bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int x, y; cin >> x >> y;
		if (y >= x) {
			cout << (y - x) << '\n';
		} else {
			if (y % 2 == x % 2) {
				cout << (x - y) / 2 << '\n';
			} else {
				cout << 2 + (x - y) / 2 << '\n';
			}
		}
	}
	return 0;
}
Editorialist's solution 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int x, y;
    cin >> x >> y;
    cout << ((x <= y) ? y - x : 1 - (x % 2 == y % 2) + (x - y + 1) / 2) << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
1 Like