Stack of Boxes - Editorial

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!

4 Likes

Hi @vichitr are we not allowed to test our solutions now? Can u pls say if that’s so, because am trying to submit the solution of this problem for past 2 days and the judge keeps running forever, if it’s not so can u please check if there’s some issue, thank u

Hey, you should be able to submit on practice and contest both pages. Will ask the team to look on the issue!

Am sorry @vichitr (also for the ping) , it seems to be a mistake from my side, after going through the submissions I see the verdicts there, extremely sorry for the trouble.

3 Likes

Good to hear that its working! Might have happened because of low internet speed!

1 Like

Instead of checking the second condition I checked that smallest element should be greater than and equal to (largest_element / 2)+(largest_element % 2).
WHich test case am i missing?

1
54817 73719 96044

OR

1
96 55 89

Your code fails here

1 Like