PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Vichitr Gandas
DIFFICULTY:
SIMPLE
PREREQUISITES:
Basic Maths
PROBLEM:
Given two integers A,B. You have to choose an integer X in the range [minimum(A,B), maximum(A,B)] such that ⌈\frac{B−X}{2}⌉+⌈\frac{X−A}{2}⌉ is maximum.
QUICK EXPLANATION
Try solving it for following 3 cases separately: 1) A=B, 2) A>B and 3) A<B.
EXPLANATION
Let’s divide the given problem in following three cases:
Case 1: A=B
In this case, we have only one choice for X that is X=A=B. In this case given sum is ⌈\frac{B−X}{2}⌉+⌈\frac{X−A}{2}⌉ = ⌈0⌉+⌈0⌉ = 0.
Case 2: A < B
Observation 1: Choose any X between the range [A, B], the given expression would always be either (B-A)/2 or (B-A)/2 + 1.
Observation 2: Its always possible to achieve the sum (B-A)/2+1 if A<B.
- Subcase (i): A-B is odd: in this case, by choosing X=A, we get the sum ⌈\frac{B−A}{2}⌉ = (B-A)/2 +1.
- Subcase (ii): A-B is even: in this case, by choosing X=A+1, we get the sum ⌈\frac{B−A-1}{2}⌉ +⌈\frac{A+1−A}{2}⌉= \frac{B-A}{2} +1 as ⌈\frac{1}{2}⌉ = 1.
Case 3: A > B
Lets solve it similar to the previous one.
- Subcase (i): A-B is odd, we get the sum (B-A)/2 for every X.
- Subcase (ii): A-B is even: in this case, by choosing X=A-1, we get the sum ⌈\frac{B−A+1}{2}⌉ +⌈\frac{A-1−A}{2}⌉= \frac{B-A}{2} +1 + ⌈\frac{-1}{2}⌉ = \frac{B-A}{2} +1 as ⌈\frac{-1}{2}⌉ = 0.
TIME COMPLEXITY:
O(1) per test case
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
assert(a >= 1 && b >= 1 && b <= 1e9 && a <= 1e9);
if (a == b) {
cout << "0\n";
} else if (b > a) {
cout << (b - a) / 2 + 1 << '\n';
} else {
if ((a - b) % 2 == 0) {
cout << (b - a) / 2 + 1 << '\n';
} else {
cout << (b - a) / 2 << '\n';
}
}
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int a, b;
cin>>a>>b;
int temp = floor((b - a) / 2.0);
if(a != b){
temp++;
}
cout<<temp<<"\n";
}
return 0;
}
Editorialist's Solution
/*
* @author: vichitr
* @date: 24th July 2021
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);
void solve() {
int A, B; cin >> A >> B;
int ans = 0;
if (A < B)
ans = (B - A) / 2 + 1;
else if (A > B) {
if ((A - B) % 2)
ans = (B - A) / 2;
else
ans = (B - A) / 2 + 1;
}
cout << ans << '\n';
}
signed main() {
fast;
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
cin >> t;
for (int tt = 1; tt <= t; tt++) {
// cout << "Case #" << tt << ": ";
solve();
}
return 0;
}
VIDEO EDITORIAL:
If you have other approaches or solutions, let’s discuss in comments.If you have other approaches or solutions, let’s discuss in comments.