BRKBKS - Editorial

PROBLEM LINK:

Div1
Div2
Practice

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 :slight_smile:

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 :smiley:

  1. 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 :slight_smile:

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

  1. 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 :slight_smile:
Related Problems

PPS: I see a pattern with a particular setter being correlated to often giving eviiiiil and haaaarrrd and trickkyyyy cakewalk problems. Do you? :wink: :stuck_out_tongue:

7 Likes

My short recursive solution

2 Likes

Maybe a bit harder (not the ussual implementation only problem), but definitely not evil (I mean there are no strange corner cases).

2 Likes

Has anyone solved this using proper use of stack and performing operations of reversal as asked in the question ?

1 Like

@alei May I know if there are any corner cases for this problem, I got an error for the somewhat same code . Here is My code.

@line 23: I guess you meant else if

instead of

if(s>=w1+w2 or s>=w2+w3)

should be

else if(s>=w1+w2 or s>=w2+w3)

otherwise for some cases it will print two answers.

Hi @alei What if the input is 1 2 2 2 how many hits are required for this?

that is not a valid test case

in question it is mentioned that she is able to break all bricks so your test case is invalid

I also put the condition s1+s3<=s because also we can reverse by one,

why my solution gives partiallly correct,
if(w1+w2+w3<=s)
cout<<“1\n”;
else if(w1+w2<=s)
cout<<“2\n”;
else if(w1+w3<=s)
cout<<“2\n”;
else if(w2+w3<=s)
cout<<“2\n”;
else
cout<<"3

Consider the test case
2 1 2 1

I have just started on this, so just wanted to understand how to interpret these questions and test cases, as you said she is able to break all the bricks, how is she not able to break all bricks in 1 2 2 2, doesn’t she require to hit bricks 6 times to break them all.

1 Like

could you please tell me why the solution does not works
What i did is
for return value 1 sum >= sum of list
for return value 3 any 2 values must be >= s
else return 2
Below is the link to my code
https://www.codechef.com/viewsolution/30905863

can u tell why my code gives 50 percent score?
https://www.codechef.com/viewsolution/31911243

#include <bits/stdc++.h>
#include
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
int s;
vector w(3);
cin>>s;
for(int i=0;i<3;i++)
cin>>w[i];
int k=accumulate(w.begin(),w.end(),0);
int rem=k%s;
int quot=k/s;
(rem==0)?cout<<quot<<endl : cout<<quot+1<<endl;
}
return 0;
}

What is wrong with my code ? Can anyone please explain ? Its showing WA

@vijju123 sir i am getting wrong answer on running this code please help
#include <stdio.h>

int main(void) {
// your code goes here
int t;
scanf("%d",&t);
while(t–){
int s,w1,w2,w3;
scanf("%d%d%d%d",&s,&w1,&w2,&w3);
if (s >= w1 + w2 || s >= w2 + w3)
printf(“2\n”);
else if (s >= w1 + w2 + w3)
printf(“1\n”);
else
printf(“3\n”);
}
return 0;
}

@nmaan11612 in the question it is mentioned she will break all bricks

Does your code work on samples and custom input? In your while loop you did “t-“ instead of “t- -“. That makes me feel you got WA and you immediately asked for help without debugging yourself.

1 Like

Thank you so much sir
I will try to be more cautious and patient next time