MAKEEQUAL - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Lavish Gupta
Tester: Abhinav Sharma
Editorialist: Taranpreet Singh

DIFFICULTY

Cakewalk

PREREQUISITES

None

PROBLEM

Chef has an array A having N elements. Chef wants to make all the elements of the array equal by repeatedly using the following move.

  • Choose any integer K between 1 and N (inclusive). Choose K distinct indices i_1 , i_2, \cdot, i_K, and increase the values of A_{i_1} , A_{i_2} , \cdots , A_{i_K} by 1.

Find the minimum number of moves required to make all the elements of the array equal.

QUICK EXPLANATION

The number of operations needed is max(A_i) - min(A_i)

EXPLANATION

We can pick any subset of given integers and increase elements in the chosen subset by 1. We want to make all elements equal.

One thing we can see is that we can only increase the elements. So it doesn’t make sense to include the largest element in any operation.

Let us perform the operations in the following manner. In current operations, pick all indices x such that A_x is the minimum element. This way, after the operation is performed, the minimum of A has increased by 1.

Let’s assume minimum of A is min(A_i) and maximum of A is max(A_i). In one operation, we can increase the minimum of A by 1. All the elements would be equal when min(A_i) = max(A_i). So it requires max(A_i) - min(A_i) operations.

Hence, all we need to do is to compute the minimum and maximum of given A and print their difference.

TIME COMPLEXITY

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

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
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;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            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,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 10000;
const int MAX_LEN = 100000;
const int MAX_VAL = 100000;
const int MAX_SUM_LEN = 100000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
 
int n;
 
 
void solve()
{
    n = readIntLn(1 , MAX_LEN) ;
    sum_len += n ;
    int arr[n] ;
    int maxi = 0 , mini = MAX_VAL ;
    for(int i = 0 ; i < n-1 ; i++)
    {
        arr[i] = readIntSp(1 , MAX_VAL) ;
        if(arr[i] > maxi)
            maxi = arr[i] ;
        if(arr[i] < mini)
            mini = arr[i] ;
    }
    arr[n-1] = readIntLn(1 , MAX_VAL) ;
    if(arr[n-1] > maxi)
        maxi = arr[n-1] ;
    if(arr[n-1] < mini)
        mini = arr[n-1] ;

    cout << maxi - mini << '\n' ;
    return ;
}
 
signed main()
{

    // fast;
    
    int t = 1;
    
    t = readIntLn(1,MAX_T);
    assert(1<=t && t<=10000);
    
    for(int i=1;i<=t;i++)
    {     
       solve();
    }
    
    assert(getchar() == -1);
    assert(1 <= sum_len && sum_len <= MAX_SUM_LEN) ;
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_len << '\n';
    cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
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;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            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,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 10000;
const int MAX_LEN = 100000;
const int MAX_VAL = 100000;
const int MAX_SUM_LEN = 100000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
 
int n;
 
 
void solve()
{
    n = readIntLn(1 , MAX_LEN) ;
    sum_len += n ;
    int arr[n] ;
    int ans = 0 ;
    for(int i = 0 ; i < n-1 ; i++)
    {
        arr[i] = readIntSp(1 , MAX_VAL) ;
    }
    arr[n-1] = readIntLn(1 , MAX_VAL) ;
    
    sort(arr,arr+n);
    cout<<arr[n-1]-arr[0]<<'\n';
    return ;
}
 
signed main()
{

    // fast;
    
    int t = 1;
    
    t = readIntLn(1,MAX_T);
    assert(1<=t && t<=10000);
    
    for(int i=1;i<=t;i++)
    {     
       solve();
    }
    
    assert(getchar() == -1);
    assert(1 <= sum_len && sum_len <= MAX_SUM_LEN) ;
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_len << '\n';
    cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class MAKEEQUAL{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int i = 0; i< N; i++){
            int x = ni();
            min = Math.min(min, x);
            max = Math.max(max, x);
        }
        pn(max-min);
    }
    //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 MAKEEQUAL().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:

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

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        int max_value = INT_MIN;
        int min_value = INT_MAX;
        int temp;
        for(int i=0; i<n; i++){
            cin>>temp;
            max_value = max(max_value, temp);
            min_value = min(min_value, temp);
        }
        cout<<max_value - min_value<<endl;
        
    }
}

What’s the problem with this code??

You forgot to read ‘n’ in your loop and everything is messed up because of this. Compiling the program with extra “-Wall -fsanitize=undefined -fsanitize=address” diagnostic options makes it much easier to debug:

$ g++ -O3 -Wall -fsanitize=undefined -fsanitize=address test.cpp
test.cpp: In function ‘int main()’:
test.cpp:12:23: warning: ‘n’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |         for(int i=0; i<n; i++){
      |                      ~^~

$ ./a.out < sample_input
test.cpp:17:27: runtime error: signed integer overflow: -2147483648 - 2147483647 cannot be represented in type 'int'
1
1

ohh such an embarassing mistake. Thanks for letting me know

What if the question doesn’t allow one to change the value of ‘k’ midway?
We needed to select k from the starting?
How could this problem be solved?