# MAKEABEQUAL - Editorial

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

1264

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];
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 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){
}
}
}
int sumN=0;
long long A[N],B[N],C[N];
void solve()
{
sumN+=N;
assert(sumN<=100000);
long long sumA=0,sumB=0;
for(int i=1;i<=N;i++)
{
if(i==N)
else
sumA+=A[i];
}
for(int i=1;i<=N;i++)
{
if(i==N)
else
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);
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 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){
}
}
}

/*
------------------------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;
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

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)

2 Likes

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

1 Like

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;
}



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
4 Likes

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

#include
using namespace std;

int main() {
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;


}

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;


}

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]);

1. 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;

}

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.

1 Like

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

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?”

2 Likes

oooo thanks !!! i got it