 # THREENUMBERS - Editorial

Author: utkarsh_25dec
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

TBD

Observation

# PROBLEM:

You have three numbers A, B, C. In one move, you can increase two of them by 1 and decrease the third by 1.
Find the minimum number of moves needed to make all three equal, or decide that it’s impossible.

# EXPLANATION:

First, notice that the given operation always flips the parity of all three numbers since each one changes by +1 or -1.
If they’re to be equal in the end, all three will have the same parity.

So, if all three don’t have the same parity initially, it’s immediately possible to say that making them equal is impossible.

Now let’s look at what we can do with our moves.

Notice that any move increases the sum (A+B+C) by exactly 1.
In particular, this means if we make them all equal to x in the end, the number of moves used will be exactly 3x - A - B - C (that is, the difference between the final sum and the initial sum).

Minimizing this is thus the same as minimizing x, so let’s attempt to do that.

Suppose A \leq B \leq C.
It’s not hard to see that if we make everything equal to x, then x \geq \frac{B+C}{2}

Why?

Let d be the initial value of B+C.

Look at the value of B+C as we perform operations.
Any move does one of two things:

• Increases B+C by 2; or
• Doesn’t change B+C.

Either way, the value of B+C cannot decrease as we perform operations.
In particular, if we end up with B = C = x, then x+x =2x \geq d, which proves our claim.

In fact, we can always achieve x = \frac{B+C}{2}
Here’s how:

• Let k = \frac{B+C}{2} be the target value.
• Recall that B and C have the same parity, so let C-B = 2y where y \geq 0.
• Perform y moves that decrease C and increase the other two.
• Now we have B = C = k, and A \leq k
• Next, alternate moves that decrease C with moves that decrease B. This way, after two moves A will increase by 2 while B and C will remain unchanged.
• The parity condition ensures that A will reach k after an even number of moves, and we’re done!

So, when A \leq B \leq C and the parity condition is satisfied, the answer is simply

3\cdot\frac{B+C}{2} - A - B - C

# TIME COMPLEXITY

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

# CODE:

Setter's code (C++)
//Utkarsh.25dec
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#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=500023;
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){
}
}
}
void solve()
{
int A, B, C;
if((A%2 == B%2) && (B%2 == C%2))
{
int d=A+B+C-min({A,B,C});
d/=2;
cout<<(3*d-A-B-C)<<'\n';
}
else
cout<<-1<<'\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";
}

Editorialist's code (Python)
for _ in range(int(input())):
a, b, c = sorted(list(map(int, input().split())))
if a%2 == b%2 and a%2 == c%2:
print(b-a + (c-b)//2)
else:
print(-1)

1 Like

@iceknight1093 I reached this step 3x-(A+B+C)

and now we need to minimize 3x-(A+B+C), so why can’t we take x=ceil(A+B+C,3)
that is x= (A+B+C+2)/3

Because it’s not always possible to reach that. If you read the next part of the editorial, it’ll tell you why you can’t get any lower than x = \frac{B+C}{2}.

For a concrete example, take A = 1, B = 100, C = 100.
\frac{A+B+C}{3} = \frac{201}{3} = 77, but it’s pretty easy to see that it’s impossible to make B and C both 77 at the same time, since at least one of them will be \geq 100.

1 Like

got your point, and one last thing to ask how do you approach these kind of problems?
Like do you get into conclusion mathematically or by doing brute force to observe some pattern and then proceed.

@iceknight1093

mathematically