PROBLEM LINK:
Setter- Alei Reyes
Tester- Encho Mishinev
Editorialist- Abhishek Pandey
DIFFICULTY:
Cakewalk
PRE-REQUISITES:
Logical Thinking, Conditionals (If-Else)
PROBLEM:
There are 3 bricks lying on top of each other, and are of width W_1,W_2 and W_3 respectively. Ada wants to break them all. She hits this stack of bricks with strength S and will break the topmost k remaining bricks such that sum of their widths is \leq S. If she is allowed to reverse the stack of bricks at will, then how many hits does she need to break all the bricks?
QUICK-EXPLANATION:
Key to AC- Since its possible to break all bricks, the answer is \leq 3. Make cases for when answer is 1, 2 or 3.
- Realize that if S \geq W_1+W_2+W_3 then only 1 hit suffices.
- If 1 hit doesnt suffices, we need either 2 or 3 hits.
- If S \geq W_1+W_2 then we can break 2 bricks in 1 hit and last one in another hit - a total of 2 hits.
- If above doesn’t happen, we can reverse the stack and see if S \geq W_3+W_2 or not. If it is so, again 2 hits suffice.
- If neither of above holds, we NEED 3 hits.
EXPLANATION:
The entire solution is there in the quick explanation. Hence, we will discuss various other solutions and some general educational things in this editorial 
Tester's Solution
This solution is described in the Quick Explanation.
Initially, the problem appears complex. Like…reversals? What… wtf? How do we approach it? Its soo complex for a cakewalk!
But thats when we need to refine the thinking. If you think of the problem with respect to making cases for each value of answer - it simplifies to a great deal.
Like, when is the answer 1? When all bricks could be broken at once, i.e. S \geq W_1+W_2+W_3.
Similarly when is the answer 2 ? If first two bricks can be broken in 1 hit, i.e. S \geq W_1+W_2. Or, we reverse the pile and are able to break last 2 bricks, i.e. if S \geq W_2+W_3.
For all other cases, answer is 3 !
A code snippet is given below-
if (s >= w1 + w2 + w3)
printf("1\n");
else if (s >= w1 + w2 || s >= w2 + w3)
printf("2\n");
else
printf("3\n");
Setter & Edtorialist's solution (Slightly Complex)
Our solution is based on the observation that reversals do not matter. So we just simulate Ada hitting and removing the bricks from the stack.
Now, thats a REALLY big thing for me to say! That you all got bamboozled and confused due to a reverse operation which is completely redundant here?
Lets prove our claim first.
Notice that if ans=3 or if ans=1, reversals do not matter at all. We only considered reversal when ans=2.
Now say I got W_1,W_2,W_3 such that I can break W_2 and W_3 in one hit, and W_1 in another hit. This is the case where we used the reversal operation in tester’s solution. What if we do not reverse it? We hit W_1 and break it in 1 hit. And then in next hit we ANYWAY break W_2 and W_3 ! Like, the answer is still 2.
Hence, under the given constraints, the reversals do not seem to matter at all. I stress again, only for given constraints.
Whats now left is just simulating the overall process, which is trivial, but not as simple to implement as tester’s solution.
A code snippet is given below-
int t;
cin>>t;
while(t--)
{
int s,w[3];
cin>>s>>w[0]>>w[1]>>w[2];
int l=0,i;
int ans=0;
while(w[0]+w[1]+w[2]>0)
{
int sum=0;
for(i=l;i<3;i++)
{
sum+=w[i];
if(sum>s)
{
l=i;
break;
}
w[i]=0;
}
//cout<<l<<" "<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl;
ans++;
}
cout<<ans<<endl;
}
SOLUTION
Setter
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
assert(ch==nxt);
break;
}
}
return v*sgn;
}
int main(){
int t=rint('\n');
assert(1<=t&&t<=64);
while(t--){
int s=rint(' ');
vector<int>w(3);
for(int i=0;i<3;i++){
w[i]=rint(i==2?'\n':' ');
assert(1<=w[i]&&w[i]<=2);
}
int ans=0;
while(!w.empty()){
int sm=0;
while(!w.empty() && sm+w.back()<=s){
sm+=w.back();
w.pop_back();
}
ans++;
}
cout<<ans<<endl;
}
assert(getchar()==EOF);
return 0;
}
Tester
#include <iostream>
#include <stdio.h>
using namespace std;
int t;
int main()
{
int test;
int i,j;
scanf("%d",&t);
for (test=1;test<=t;test++)
{
int s,w1,w2,w3;
scanf("%d %d %d %d",&s,&w1,&w2,&w3);
if (s >= w1 + w2 + w3)
printf("1\n");
else if (s >= w1 + w2 || s >= w2 + w3)
printf("2\n");
else
printf("3\n");
}
return 0;
}
Editorialist
/*
*
********************************************************************************************
* AUTHOR : Vijju123 *
* Language: C++14 *
* Purpose: - *
* IDE used: Codechef IDE. *
********************************************************************************************
*
Comments will be included in practice problems if it helps ^^
*/
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
//I never understand why people put useless functions at top of code. Makes it so unreadable ughhhh.
int mod=pow(10,9)+7;
int fastExpo(long long a,long long n, int mod)
{
a%=mod;
if(n==2)return a*a%mod;
if(n==1)return a;
if(n&1)return a*fastExpo(fastExpo(a,n>>1,mod),2,mod)%mod;
else return fastExpo(fastExpo(a,n>>1,mod),2,mod);
}
inline void add(vector<vector<int> > &a,vector<vector<int> > &b,int mod)
{
for(int i=0;i<a.size();i++)for(int j=0;j<a[0].size();j++)b[i][j]=(b[i][j]+a[i][j])%mod;
}
void multiply(vector<vector<int> > &a, vector<vector<int> > &b,int mod,vector<vector<int> > &temp)
{
assert(a[0].size()==b.size());
int i,j;
for(i=0;i<a.size();i++)
{
for(j=0;j<b[0].size();j++)
{
temp[i][j]=0;
for(int p=0;p<a[0].size();p++)
{
temp[i][j]=(temp[i][j]+1LL*a[i][p]*b[p][j])%mod;
}
}
}
}
void MatExpo(vector<vector<int> > &arr,int power,int mod)
{
int i,j,k;
vector<vector<int> >temp,temp2,temp3;
vector<int> init(arr[0].size());
for(i=0;i<arr.size();i++){temp.push_back(init);}
temp3=temp;
temp2=temp;
for(i=0;i<arr.size();i++)temp3[i][i]=1;
while(power>0)
{
if(power&1)
{
multiply(arr,temp3,mod,temp);
swap(temp3,temp);
}
multiply(arr,arr,mod,temp2);
swap(arr,temp2);
power>>=1;
}
swap(arr,temp3);
}
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<<"<="<<x<<"<="<<r<<endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
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){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
vector<int> primes;
int isComposite[1000001]={1,1};
void sieve()
{
int i,j;
for(i=2;i<=1000000;i++)
{
if(!isComposite[i])
{
primes.push_back(i);
isComposite[i]=i;
}
for(j=0;j<primes.size() and i*primes[j]<=1000000;j++)
{
isComposite[primes[j]*i]=i;
if(i%primes[j]==0)break;
}
}
}
int main() {
// your code goes here
#ifdef JUDGE
string in,out;
cin>>in>>out;
in+=".in";
if(in!="z.in")
out+=".out";
else out+=".in";
if(in!="z.in")
freopen(in.c_str(), "rt", stdin);
freopen(out.c_str(), "wt", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
srand(time(NULL));
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int t;
cin>>t;
while(t--)
{
int s,w[3];
cin>>s>>w[0]>>w[1]>>w[2];
int l=0,i;
int ans=0;
while(w[0]+w[1]+w[2]>0)
{
int sum=0;
for(i=l;i<3;i++)
{
sum+=w[i];
if(sum>s)
{
l=i;
break;
}
w[i]=0;
}
//cout<<l<<" "<<w[0]<<" "<<w[1]<<" "<<w[2]<<endl;
ans++;
}
cout<<ans<<endl;
}
assert(getchar()==-1);
return 0;
}
Time Complexity=O(1) for tester and O(N) for setter and editorialist where N=\text{number of bricks}
Space Complexity=O(1) for tester and O(N) for setter and editorialist where N is same as defined above.
CHEF VIJJU’S CORNER 
- The general version of this problem is not this simple! With respect to above, try to answer the following-
- When I said “under given constraints, reversals do not matter” , exactly what constraint am I referring to? N=3 ? W_i=1 \ or \ 2? Or both of them? Proof via counterexample is acceptable as well.
- How will you solve the general case?
Hint for General Case
The general case can be solved with DP . One can use multiple approaches, right now DP + Memoization comes to mind which should work in O(N^2) or O(N^3) depending on how you implement it.
Thanks to @alei for suggesting to discuss this, my solution based on his/her hints builds a table dp[L][R] representing the solution for range [L,R]. We find answer for all the ranges and the final answer gets stored in dp[1][N].
Base case being dp[i][i]=1.
The recurrence which I can think of is something like this-
Say if we are calculating answer for range [L,R], where we are adding the L'th brick on top of stack. We see how many bricks Ada can break if the brick is on top of stack, and if the brick is on bottom of stack. Say all bricks till some value X break. Then the recurrence should be only the lines of DP[L][R] = 1+min(DP[X_{top}][R], DP[L][X_{bottom}]). Here X_{top} represents if the brick is put on top of stack, and X_{bottom} represents if the brick is put on bottom of stack.
Please note that I have not implemented my solution for the case, so I will appreciate any feedback here
Setter's Notes
Another possible solution:
the answer can only be \text{1, 2 or 3}
-
if S \geq W_1+W_2+W_3 then 1
-
else if S \geq W_1+W_2 then 2 (or S \geq W_3+W_2 if we use reversal)
-
otherwise 3
- A solution is given below, either prove its correctness or tell why its wrong:
Solution 1-
if (s >= w1 + w2 || s >= w2 + w3)
printf("2\n");
else if (s >= w1 + w2 + w3)
printf("1\n");
else
printf("3\n");
if (s < w1 + w2 + w3)
printf("3\n");
else if (s < w1 + w2 || s < w2 + w3)
printf("2\n");
else
printf("1\n");
Answer for Above
- Solution 1 fails for cases where answer is 1. It will execute first condition and print 2.
- The second solution is also wrong!! See when it prints 2 and when it prints 3
