How did you got the intuition?
1 Like
the obvious naive approach was to loop from min(a,b) to max(a,b) and find the satisfying x, but instead of this,binary search is optimal once you understand manipulating low and high, understood the pattern of manipulating low and high variables by looking at a few test cases.
The given result function is a zig-zag hence binary search is a wrong approach here. It passed because the given function takes only two distinct values at most, you would always try those 2 choices somehow.
1 Like
Hey I have published it now. I made it private earlier because some work was pending.
1 Like
Now published
- I figured out the zigzag nature of the function, but my submission was still WA. can you give some feedback on the code?
- in the solution what is the purpose of this
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include
using namespace std;
int main() {
long long int t; cin>>t;
while(t–){
long long int a,b;cin>>a>>b;
long long int x=min(a,b);
long long int r1 = ceil((float)(b-x)/2)+ceil((float)(x-a)/2);
x++;
long long int r2 = ceil((float)(b-x)/2)+ceil((float)(x-a)/2);
if(x>max(a,b)){
cout<<r1<<endl;
}
else{
x= r1>r2?r1:r2;
cout<<x<<endl;
}
}
return 0;
}
did this got accepted? I did the same code but it didnt pass the test cases.
so in this problem we have to check for x in a,a+1,a-1 manually and then conclude the cases
I tried reducing the given expression in the problem into (b - a + 2) / 2. Why is this incorrect?
Because they are not just fractions. You are ceiling them up. Examples were already given in the problem statement.
Think of a test case where your logc fails.
a = 3
b = 3
Expected answer: 0
Your answer: 1
If a=b=3 and I take x=2.
Ceil(0.5)=1 and ceil (-0.5)=0, then answer should be 1, but according to the editorial the answer should be 0.
Please correct me, if I am wrong
X should lie between min(a,b) and max(a,b)
hence, 2 is not a valid x
Thanks…
My bad…
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t–) {
int a,b,x;
cin>>a>>b;
int arr[100];
for(x=min(a,b); x<=max(a,b) ;x++) {
int e = ceil((b-x)*0.5);
int m = ceil((x-a)*0.5);
arr[x] = e + m;
}
int maxx = arr[min(a,b)];
for(x=min(a,b); x<=max(a,b);x++) {
if (arr[x] > maxx)
maxx = arr[x];
}
cout<<maxx<<endl;
}
return 0;
}[quote=“vichitr, post:1, topic:92689, full:true”]
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;
}
[details=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;
}There is no need to check even or odd in code:
ll t;
cin >> t;
while (t--) {
ll a, b, res = 0;
cin >> a >> b;
if (a < b) {
res = 1 + (b - a) / 2;
} else {
res = (b - a + 1) / 2;
}
cout << res << "\n";
}
When a>b, f(B)={\lceil}\frac{B-A}{2}{\rceil},f(B+1)={\lceil}\frac{B-A+1}{2}{\rceil}, we known {\lceil}\frac{B-A+1}{2}{\rceil}\geqslant{\lceil}\frac{B-A}{2}{\rceil} when A > B. If B-A is odd they are equal.
1 Like
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–){
int a,b;
cin>>a>>b;
int ma=max(a,b);
int mi=min(a,b);
int r=-1e6;
for(int i=mi;i<=ma;i++){
int ans=ceil((b-i)/2)+ceil((i-a)/2);
r=max(ans,r);
}
cout<<r<<endl;
}
return 0;
}
why this code is giving wrong answer for some test cases?
Your code is giving TLE.
And maybe you should take r as -1e9 not -1e6.
Note: Don’t use inbuilt ceil function . Make your own function for calculating ceil.
Function for calculating ceil value of m/n i.e. ceil(m/n)
int find_ceil ( int m , int n ){
return ( m+n-1)/n;
}
buddy you are doing integer division change it to double
this doesn’t work. shows wrong answer