 # MAX_DIFF - Editorial

Setter: Lavish Gupta
Tester: Samarth Gupta
Editorialist: Taranpreet Singh

Cakewalk

Basic Math

# PROBLEM

Given two integers N and S, Find maximum possible value of |T_1 - T_2| if 0 \leq T_1, T_2 \leq N and T_1+T_2 = S

It is guaranteed that for N and S in input, there exists at least one pair (T_1, T_2) such that 0 \leq T_1, T_2 \leq N and T_1+T_2 = S

# QUICK EXPLANATION

• If S \leq N, we can choose pair T_1 = 0 and T_2 = S to obtain absolute difference S, which is maximum possible.
• If N \leq S \leq 2*N, we can choose pair T_1 = N and T_2 = S-N to obtain absolute difference 2*N-S
• There cannot be a case with S \gt 2*N as that requires at least one of T_1 and T_2 to be \gt N which is not allowed. Similarly for S \lt 0.

# EXPLANATION

I’d explain two thought processes here.

### Thought Process 1

Let’s assume we only require 0 \lt T_1, T_2 and T_1 + T_2 = S. (Upper bound N is ignored). It is easy to see that if we choose T_1 = 0 and T_2 = S, we obtain maximum possible absolute difference. Increasing T_1 only decreases T_2 which reduces absolute difference. So we achieve absolute difference S.

In our problem, T_1,T_2 \leq N stops us from choosing above, as it may happen that T_2 = S \gt N. So we have to reduce T_2 by at least S-N. Let’s do that. T_1 = S-N and T_2 = N is the pair we get, and we don’t need to do any more changes, as reducing T_2 now only reduces absolute difference. So, we obtain an absolute difference 2*N-S.

### Thought Process 2

In most min-max problems, it is always good to check out boundary points. We can prove that the absolute difference is maximized only when at least one of T_1 and T_2 are on end-points (0 or N).

Based on the above, we can try all pairs where T_1 is either 0 or N (There are only two such pairs). If a valid pair is formed, then take the maximum of absolute difference among valid pairs.

### Tip

The required answer is min(S, 2*N-S). The proof is left as an exercise.

# TIME COMPLEXITY

The time complexity is O(1) per test case.

# SOLUTIONS

Setter's Solution
#define ll long long
#define rep(i , n) for(ll i = 0 ; i < n ; i++)
#include<bits/stdc++.h>

ll max(ll a , ll b){if(a > b) return a ; return b ;}
ll min(ll a , ll b){if(a < b) return a ; return b ;}

using namespace std ;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

ll t ;
cin >> t ;
//t = 1 ;

while(t--)
{
ll sum , max_marks ;
cin >> max_marks >> sum ;

if(sum <= max_marks)
{
cout << sum << endl ;
continue ;
}
cout << (2*max_marks - sum) << endl ;
}

return 0;
}

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

long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
int sum = 0;
while(t--){
assert(0 <= s && s <= 2*n);
int t1, t2;
t2 = s;
t2 = min(t2, n);
t1 = s - t2;
cout << abs(t2 - t1) << '\n';
}
return 0;
}

Editorialist's Solution
import java.util.*;
import java.io.*;
class MAX_DIFF{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), S = ni();
int d1 = 0, d2 = S;
if(d2 > N){
int d = d2-N;
d1 += d;
d2 -= d;
}
pn(d2-d1);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new MAX_DIFF().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always. 1 Like

#include
#include
using namespace std;
int main()
{
int t;
cin >> t;
while (t–)
{
int n, s;
cin >> n >> s;
if (n >= s)
cout << s << endl;
else if(s-n<n)
cout<<abs(s-2*n)<<endl;
}
return 0;
}

I wrote this code for the same problem, Can anyone explain, why this is wrong?

else if(s-n<n)
May be this should be
s-n<=n

this is the logic👇
if (N>=S)
{
num1=S;
}
else if(S<=(2N)){
num1=2
N-S;
}

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

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t,n,s,i,j,flag=0;
cin>>t;
while(t--) {
cin>>n>>s;
for(i=n;i>=0;i--) {
for(j=0;j<=n;j++) {
if(i+j == s)
{  cout<<abs(i-j)<<endl;
flag++;
break; } }
if(flag>0)
break;
} }
return 0; }


// For which test case, I am getting WA ?