MAX_DIFF - Editorial

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. :slight_smile:

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 ?