PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Lavish Gupta
Tester: Samarth Gupta
Editorialist: Taranpreet Singh
DIFFICULTY
Cakewalk
PREREQUISITES
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) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
t = readIntLn(1, 1000);
int sum = 0;
while(t--){
int n = readIntSp(1, 1e5);
int s = readIntLn(1, 2e5);
assert(0 <= s && s <= 2*n);
int t1, t2;
t2 = s;
t2 = min(t2, n);
t1 = s - t2;
cout << abs(t2 - t1) << '\n';
}
readEOF();
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;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
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());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 