CEILSUM - Editorial

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.

1 Like

if(a==b) x := a;
else x := min(a,b) + 1;

I think, this will be a sufficient condition.

3 Likes

Can you please tell me how did you figure out the formula for the conditions A>B and B>A.

5 Likes

#include<iostream
#include<cmath

using namespace std;

int main(void)

{

int T{};

cin>>T;

while(T--)

{

    int A,B;

    cin>>A>>B;

    if(A==B)

    {

        cout<<0<<endl;

    }

else if(((A%2==0)&&(B%2==0))||((A%2!=0)&&(B%2!=0)))

    cout<<((B-A)/2)+1<<endl;

else

{

    cout<<ceil((B-A)/2.0)<<endl;

}

}

return 0;

}
This gives “WA”!
What is wrong with my code?
It passes all the testcase.

2 Likes

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;
import java.lang.Math;
import java.util.Arrays;
import java.util.Collections;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
try {
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()){
String testCases = sc.nextLine();
int j =0;

    while(j < Integer.parseInt(testCases))
	{
	    
	    int A = sc.nextInt();
	    int B = sc.nextInt();
	    List<Integer> list = new ArrayList<>();

	    for(int i = Math.min(A, B) ; i<= Math.max(A, B) ; i++)
	    {
	         list.add(i);
	        
	    }
	    
	     Integer sum[] = new  Integer [list.size()];
	    
	    for(int i = 0 ; i < list.size() ; i++)
	    {
	        sum[i] = (int) Math.ceil((float)( B-list.get(i) ) / 2 ) + (int) Math.ceil((float)( list.get(i)-A ) / 2 );
	        
	      //  System.out.println(sum[i]);
	    }
	    
           List<Integer> sumList = Arrays.asList(sum); 
           Integer max = Collections.max(sumList);  
	    
	    System.out.println(max);
	
	j++;
	  
	}
	         
	    }
	    sc.close();
	    
	} catch(Exception e) {
	    
	}
}

}

1 Like

#include

using namespace std;

int main()

{

 int t;

cin>>t;

while(t--)

{  

     int a,b,sum=0;

    cin>>a>>b;

    if(a==b)

    sum=0;

    else if(b>a)

    {  

       sum=  ((b-a)/2)+1;

    }

    else

    {  

        if((a-b)%2==0)

        { sum=((b-a)/2)+1;}

        else

        sum= (b-a)/2;

    }

    cout<<sum<<endl;

}

return 0;

}

Binary Search approach

#include <bits/stdc++.h>
using namespace std;

typedef long double ld;
typedef long long ll;

ld op(ld a,ld b,ld x){
	return (ceil((b-x)/2)+ceil((x-a)/2));
}

void solve(ll a,ll b){ 
	ll low=min(a,b);
	ll high=max(a,b);
	ll mid;
	ld res=LONG_MIN;

	while(low<=high){
		mid=(low+high)/2;

		if(op(a,b,mid)>res){
			low=mid+1;
			res=max(res,op(a,b,mid));
		}else{
			high=mid-1;
		}
	}

	cout<<(int)res<<"\n";
}


int main(){
	ll t;
	cin>>t;

	while(t--){
		ld a,b;
		cin>>a>>b;
		solve(a,b);
	}
}
7 Likes

@soumyadeep_21 editorial for last problem is not visible.

1 Like

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

  1. I figured out the zigzag nature of the function, but my submission was still WA. can you give some feedback on the code?
  2. 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