MAKEABEQUAL - Editorial

iceknight1093 · August 24, 2022, 5:31pm

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Utkarsh Gupta
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

1264

PREREQUISITES:

Observation

PROBLEM:

You have two arrays A and B of length N. In one step, you can add 1 to an element of A and an element of B. Find the minimum number of moves to make A and B equal.

EXPLANATION:

First, note that each move increases the sum of both A and B by exactly one. So, if initially A and B have different sums, they can never be made equal (since they must have the same sum when they are equal).

Now, assume sum(A) = sum(B). Let’s look at a specific index i (1 \leq i \leq N).

If A_i = B_i, we don’t need to do anything
If A_i \lt B_i, we need to use B_i - A_i operations on A_i to attain equality at this index.
If A_i \gt B_i, we need to use A_i - B_i operations on B_i to attain equality at this index.

Let x = \sum_{i=1}^N \max(0, B_i - A_i). As noted from above, x is the minimum number of operations we need to perform on indices of A.
Similarly, let y = \sum_{i=1}^N \max(0, A_i - B_i) be the minimum number of operations we need to perform on B.

Clearly, the answer is at least \max(x, y).

In fact, given the condition that sum(A) = sum(B), we have x = y, and this is exactly the answer.

Proof

Note that x - y = \sum_{i=1}^N (B_i - A_i), which equals sum(B) - sum(A). Since these are equal by assumption, x-y = 0 and hence x = y.

Since x = y, each of the x operations that need to be made on an element of A can be matched with one of the y operations that need to be made on an element of B, thus completing the proof.

Computing the value of x and/or y can be done in \mathcal{O}(N) with a simple loop.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (C++)

//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=100023;
bool vis[N];
vector <int> adj[N];
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,' ');
}
int sumN=0;
long long A[N],B[N],C[N];
void solve()
{
    int N=readInt(2,100000,'\n');
    sumN+=N;
    assert(sumN<=100000);
    long long sumA=0,sumB=0;
    for(int i=1;i<=N;i++)
    {
        if(i==N)
            A[i]=readInt(1,1000000000,'\n');
        else
            A[i]=readInt(1,1000000000,' ');
        sumA+=A[i];
    }
    for(int i=1;i<=N;i++)
    {
        if(i==N)
            B[i]=readInt(1,1000000000,'\n');
        else
            B[i]=readInt(1,1000000000,' ');
        sumB+=B[i];
    }
    if(sumA!=sumB)
    {
        cout<<-1<<'\n';
        return;
    }
    for(int i=1;i<=N;i++)
        C[i]=max(A[i],B[i]);
    long long ans=0;
    for(int i=1;i<=N;i++)
        ans+=(C[i]-A[i]);
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,20000,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester's code (C++)

#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 = 20000;
const int MAX_N = 100000;
const int MAX_A = 1000000000;
const int MAX_SUM_N = 100000;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_len=0;

void solve()
{
    int n;
    n = readIntLn(1, MAX_N);
    sum_len += n;
    assert(sum_len <= MAX_SUM_N);
    int a[n],b[n];
    for(int i = 0; i < n - 1; i++) a[i] = readIntSp(1, MAX_A);
    a[n - 1] = readIntLn(1, MAX_A);
    for(int i = 0; i < n - 1; i++) b[i] = readIntSp(1, MAX_A);
    b[n - 1] = readIntLn(1, MAX_A);
    int delta = 0; long long int ans = 0;
    for(int i = 0; i < n; i++) {
        delta += a[i] - b[i];
        ans += abs(a[i] - b[i]);
    }
    ans /= 2;
    if(delta) {
        cout << "-1\n";
        return;
    }
    cout << ans << "\n";
}

signed main()
{
    //fast;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif


    int t = readIntLn(1, MAX_T);

    for(int i=1;i<=t;i++)
    {
        solve();
    }

    assert(getchar() == -1);
}

Editorialist's code (Python)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    dif = sum = 0
    for i in range(n):
        dif += a[i] - b[i]
        sum += abs(a[i] - b[i])
    print(sum//2 if dif == 0 else -1)

belunymous · August 24, 2022, 7:28pm

Can someone please explain this.
By intuition i know that x and y must be equal but can’t understand this line mathematically.

codetantra · August 25, 2022, 12:26am

I just take the diff of A&B. Now the diff vector will have both positives and negatives. For a possible solution the sum(diff) should be zero.

if the sum of positives in diff and negatives in diff are equal, the sum of positives is the answer as each operation changes number by 1 only.

C++ Solution

llint T; cin>>T;
while(T--){
          int n; cin>>n;
          vector<int> A(n,0),B(n,0);
          for(auto &a:A) cin>>a;
          for(auto &b:B) cin>>b;
          int sum_p =0; int sum_n = 0;
          for(int i=0;i<n;i++) {
                    int x = (A[i]-B[i]);
                    if(x > 0) sum_p += x; else sum_n += x;
          }
          if((sum_p+sum_n)!=0) cout<<"-1"<<endl;
          else cout<<sum_p<<endl;
}

iceknight1093 · August 25, 2022, 6:04am

That line is the first step of formally proving x = y, and can be obtained by pure algebraic manipulation: no intuition needed.

We want to prove that x = y. One way is to show that x - y = 0.

To do that, the obvious first step is to actually compute x-y. Now you may note that:

x gives the sum of all B_i - A_i where B_i \geq A_i
y gives the sum of all A_i - B_i where A_i \geq B_i
So, -y gives the sum of all B_i - A_i where A_i \geq B_i
Add them together, x + (-y) gives the sum of all B_i - A_i, because every index i is covered in one of the two cases above.
\sum_{i=1}^N (B_i - A_i) can be split into (\sum_{i=1}^NB_i) - (\sum_{i=1}^NA_i)
This is simply sum(B) - sum(A), which we know is zero using the fact that we assumed sum(A) = sum(B) right at the start
So, x-y = 0, which is what we wanted to show

super_fluid · August 28, 2022, 5:03am

Can someone please suggest what issue I might be having so as to not clear all the testcases:

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n, i, count = 0;
cin>>n;
int a[n], b[n];
for(i = 0; i<n; i++)
cin>>a[i];
for(i=0; i<n; i++)
cin>>b[i];

    for(i=0; i<n; i++)
    {
        while(a[i]<b[i])
        {
            a[i]++;
            count++;
        }
    }
    
    int max_count = count;
    
    for(i=0; i<n; i++)
    {
        while(b[i]<a[i])
        {
            b[i]++;
            count--;
        }
    }
    
    if(count == 0)
        cout<<max_count<<endl;
    else
        cout<<-1<<endl;
}
return 0;

}

demo_neel · August 29, 2022, 12:24pm

what is wrong with my code it doesn’t pass all test cases?

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);      //this is fast I/O (inputput output) use header file <cstdio>
ll t; cin>>t;
while(t--){
    ll n; cin>>n;
    ll a[n], b[n];
    for(int i=0; i<n; i++)
        cin>>a[i];
    
    for(int i=0; i<n; i++)
        cin>>b[i];

    ll sum1=0 , sum2 = 0;       
    ll max1=0, max2=0;
    for(int i=0; i<n; i++){
        if(a[i]>b[i]){
            sum1+= a[i]-b[i];           //total positive
            max1 = max(max1,a[i]-b[i]);
        }
        else if(b[i]>a[i]){
            sum2 += a[i]-b[i];            //total negative
            max2 = max(max2,b[i]-a[i]);
        }
    }

    if(sum1+sum2 !=0)
        cout<<-1<<endl;
    else{
        ll ans = max(max1, max2);
        cout<<ans<<endl;
    }


    
  
    
}
return 0;

}

demo_neel · August 29, 2022, 12:32pm

another Q this gave correct ans by my quoted lines are wrong
1)count = max(count, abs(a[i]-b[i]));
2)count += abs(a[i]-b[i]);

gave wrong ans while (2) gave correct why how can we be sure it always will be /2 and not anything else?

ll t;cin>>t;

while(t--){

    ll n; cin>>n;

    ll a[n], b[n];

    for(int i=0; i<n; i++)

        cin>>a[i];

    for(int i=0; i<n; i++)

        cin>>b[i];

    ll sum = 0, count=0;

    for(int i=0; i<n; i++){

        sum += a[i]-b[i];               //since x=y so we can make x-y=0

        //count = max(count, abs(a[i]-b[i]));

        count += abs(a[i]-b[i]);

    }

    if(sum == 0)

        cout<<count/2<<endl;

    else

        cout<<-1<<endl;

}

iceknight1093 · August 30, 2022, 5:53am

When you compute \sum_{i=1}^N |A_i - B_i|, in terms of the values defined in the editorial it is exactly x+y.

Since x = y, this is just 2x. The answer is x so you divide this by 2 to get the answer.

demo_neel · August 30, 2022, 12:12pm

oooh ok thanks , but *count = max(count, abs(a[i]-b[i])) should also give correct answer right so why did it give WA?

iceknight1093 · August 30, 2022, 1:26pm

If you think about it, your question is essentially “why is the maximum element of a set not always the same as half of its sum?”

demo_neel · August 30, 2022, 2:08pm

oooo thanks !!! i got it