About the Problem
| Setter(s) | Janmansh Agarwal |
| Tester(s) | Vichitr Gandas |
| Difficulty | Cakewalk |
| Topics | Adhoc, Maths |
| Practice | Link |
| Contest | Link |
Solution Idea
In one operation we are removing total of 4 boxes, hence the sum of the number of boxes in the stacks should be divisible by 4 . Now, suppose we remove 2 boxes from first stack, total of x times, remove 2 boxes from second stack y times and remove 2 boxes from third stack z times. Now if we are able to clear all the boxes from all three stacks then following conditions would hold -
A = 2*x + y + z,
B = x + 2*y + z,
C = x + y + 2*z .
Because total number of removed boxes should be equal to initial number of boxes in each stack.
From above three conditions we get,
A + B + C = 2*x + y + z + x + 2*y + z + x + y + 2*z = 4*(x+y+z) .
From here total number of moves,
x+y+z = (A+B+C)/4.
Total number of moves should be an integer hence (A+B+C) should be divisible by 4.
Also the minimum element should be greater than total number of moves hence
min(A,B,C) >= x+y+z
=> min(A,B,C) >= (A+B+C)/4
Complexity Analysis
Time Complexity: \mathcal{O}(1) as we just need to check two conditions.
Space Complexity: \mathcal{O}(1) as no extra space needed.
Codes
Setter's Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll a[3];
cin>>a[0]>>a[1]>>a[2];
ll sum=0;
sum += a[0]+a[1]+a[2];
sort(a,a+3);
ll k=sum;
if(sum%4){
cout<<"NO\n";
return;
}
k/=4;
if(a[0]>=k){
cout<<"YES\n";
return;
}
cout<<"NO\n";
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll t=1;
cin>>t;
while (t--){
solve();
}
return 0;
}
Tester's Code
/***************************************************
@author: vichitr
Compiled On: 02 Mar 2021
*****************************************************/
#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;
signed main()
{
fast;
int t = 1;
cin >> t;
assert(t <= 1e5);
for(int i = 1; i <= t; i++)
{
int a, b, c; cin >> a >> b >> c;
assert(a > 0 and a <= 1e9);
assert(b > 0 and b <= 1e9);
assert(c > 0 and c <= 1e9);
if((a + b + c) % 4 == 0 and min({a, b, c}) >= (a + b + c) / 4)
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
If you have used any other approach, share your approach in comments!
If you have any doubts, ask them in comments!