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.


Setter's Code
using namespace std;
#define ll long long

void solve(){
  ll a[3];
  ll sum=0;
  sum += a[0]+a[1]+a[2];
  ll k=sum;

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  ll t=1;
  while (t--){
  return 0;
Tester's Code

@author: vichitr
Compiled On: 02 Mar 2021

#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;

signed main()
    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)
    return 0;

If you have used any other approach, share your approach in comments!
If you have any doubts, ask them in comments!


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.


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