CEILSUM - Editorial

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