CHEFNWRK - Editorial

PROBLEM LINK:

Practice
Contest
Video Editorial

Setter: Ritesh Gupta
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Cakewalk

PREREQUISITES:

Ad-hoc and Greedy

PROBLEM:

You have given N boxes, where the weight of i-th box is W_i. Chef has to take all the boxes by making one or more round trips. In each trip, he can pick any number of boxes as long as the total weight doesn’t exceed K. Also, you can pick up the i-th box only if all the boxes between Chef’s home and the i-th box have been either moved or picked up in current trip.

EXPLANATION:

First, let us check that is it possible to pick every box, i.e. W_i \leq K, if for any box W_i > K then it is not possible to pick this box and answer will be -1.
In the first trip, start at box 1 and keep on going to the right until the total sum of boxes \leq K. (greedily picking up as many boxes as possible).

int pickedUp = 0;
while((i < N) && (weight[i]+pickedUp <= K)) { // try to go as right as you can.
	pickedUp += weight[i];
	i ++;
}

If all the boxes are picked up then stop and the answer is 1 else suppose you can pick up till box i, so now start the second trip from box i+1. Continue the process until you have picked up all the boxes.

TIME COMPLEXITY:

  • In each test case we are doing a single linear iteration over the weight of boxes and, as the number of trips can’t be more than the number of boxes(when the answer is possible). So total time complexity per test case is O(N).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t;
    cin >> t;
 
    while(t--)
    {
        int n,k;
        cin >> n >> k;
 
        int ans = 0;
        int sum = 0;
 
        vector <int> v(n);
 
        for(int i=0;i<n;i++)
            cin >> v[i];
 
        bool flag = false;
 
        for(int i=0;i<n;i++)
        {
            if(v[i] > k)
                flag = true;
        }
 
        if(flag)
        {
            cout << -1 << endl;
            continue;
        }
 
        for(int i=0;i<n;i++)
        {
            sum += v[i];
 
            if(sum > k)
            {
                ans++;
                sum = v[i];
            }
        }
 
        if(sum > 0)
            ans++;
 
        cout << ans << endl;
    }
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
//#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
    uniform_int_distribution<int> uid(0,lim-1);
    return uid(rang);
}
 
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;
            }
            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,' ');
}
 
int w[1005];
void solve() {
    int n,k;
    n=readIntSp(1,1000);
    k=readIntLn(1,1000);
    fr(i,1,n) {
        if(i!=n)
            w[i]=readIntSp(1,1000);
        else
            w[i]=readIntLn(1,1000);
    }
    int ans=1,we=0;
    fr(i,1,n) {
        if(w[i]>k) {
            cout<<-1<<endl;
            return;
        }
        we+=w[i];
        if(we>k) {
            ans++;
            we=w[i];
        }
    }
    cout<<ans<<endl;
}
 
signed main() {
    ios_base::sync_with_stdio(0),cin.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    cout<<fixed<<setprecision(8);
    int t=readIntLn(1,100);
//  cin>>t;
    while(t--)
        solve();
    assert(getchar()==EOF);
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

void solveTestCase() {
	int N, K;
	cin >> N >> K;
	vector<int> weight(N);
	for(int i = 0; i < N; i ++) {
		cin >> weight[i];
	}
	for(int i = 0; i < N; i ++) {
		if(weight[i] > K) { // If there is a box with weight higher than K, then chef can't lift it so answer is impossible or -1.
			cout << -1 << '\n';
			return;
		}
	}
	int trips = 0, id = 0;
	while(id < N) {
		trips ++;
		int pickedUp = 0;
		while((id < N) && (weight[id]+pickedUp <= K)) { // try to go as right as you can.
			pickedUp += weight[id];
			id ++;
		}
	}
	cout << trips << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); // fast IO
	cin.tie(0);
	cout.tie(0);

	int testCase;
	cin >> testCase;
	for(int i = 1; i <= testCase; i ++) {
		solveTestCase();
	}

	return 0;
}

Video Editorial

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

Hey psychik,

Thanks for the Editorial. Can you please look at my code and let me know what I am doing wrong?

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner scanner = new Scanner(System.in);

    int wTrip=0, k=0, n=0, trips;
    int[] wArray;
    int testCases = scanner.nextInt();
    boolean flag;

    while( testCases > 0 ){
        testCases--;
        trips = 0; // count number of trips
        n = scanner.nextInt();
        k = scanner.nextInt();
        wArray = new int[n+1]; // the last box is zero
        wTrip=0;    // weight for the current trip
        flag = true; // boolean to check if a box is heavier than k


        for (int i = 0; i < (n+1) && flag; i++) {
            if(i < n) {
                wArray[i] = scanner.nextInt();
            }

            wTrip = wTrip + wArray[i];
            if(wTrip > k){
                trips++;
                wTrip = wArray[i];
            }
            if(wArray[i] > k){
                flag = false;
            }
        }
        if(wTrip > 0){
            trips++;
        }

        if( flag ){
            System.out.println(trips);
        }else {
            System.out.println("-1");
        }
    }
}

}

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t–>0) {
int n=sc.nextInt();
int k=sc.nextInt();
int []arr=new int[n];
for(int i=0;i<n;i++) {
arr[i]=sc.nextInt();
}
int count=0;
int flag=1;
for(int i=0;i<n;i++) {
int s=k-arr[i];
if(s<0) {
System.out.println(-1);
flag=0;
break;
}
if(arr[i]!=0)
count+=1;
int j=i+1;
while(s!=0 && j<n && s>=arr[j]){
s-=arr[j];
arr[j]=0;
j++;
}
}
if(flag==1)
System.out.println(count);
}
// your code goes here
}
}
i think my approach is also similar but,instead of adding elements till <=k,i subtracted elements from k till it becomes zero by using variable s,but still my answer is wrong,can you guide me

I think you are trying to take n+1 boxes in each test case instead of n.

I tried a lot to solve but couldn’t solve even one question,
what’s wrong with this solution
int main()

{
int t;
cin>>t;
while(t–)
{

    long long int n,k,s=0;

    long long int count=1,f=1; 

    cin>>n>>k; 

    long long int a[n];

    for(int i=0;i<n;i++) 

     { 

         cin>>a[i];

         if(a[i]>k) {f=0; break;}

     } 

     if(f==0) cout<<"-1"<<endl;

     else

    {

      for(int i=0;i<n;i++) 

      {

              s+=a[i];

            //cout<<"i is "<<i<<" s is "<<s<<" c is "<<c<<endl;

            if(s>k){

                count++;
                i--;
                s=0;
                }
      } 

      cout<<count<<endl;

     }  //end of else condition

  

}

return 0;

}

I think you are initializing your count variable with 1 instead of 0.

u are not counting last trip
n=2 k=3
array=2,2
trip=2
but ur answer is 1

Video explanation : https://www.youtube.com/watch?v=N_qU_oBruAI

First of thank you for the reply.
But I don’t think that should make a difference as the weight for the last box is 0 (zero).
Moreover, if you see the code

if(wTrip > 0){
trips++;
}

if my wTrip is equal to wArray[n], when I am taking n+1 boxes, i.e 0 (zero) it will not count that as a trip.

I initialized count=1 just for handling last weight in array .
however, this code ran and passed all test cases , I don’t see much difference from mine
indent preformatted text by 4 spaces
#include

using namespace std;

int main()

{

int t; 

cin>>t;

while(t--)

{

    long long int n,k,s=0;

    long long int count=1,f=1; 

    cin>>n>>k; 

    long long int a[n];

    for(int i=0;i<n;i++) 

     { 

         cin>>a[i];

         

     } 

              

      for(int i=0;i<n;i++) 

      {

              if(a[i]>k) {f=0; break;}

          else 

          {

              s+=a[i];

             //cout<<"i is "<<i<<" s is "<<s<<" c is "<<c<<endl;

             if(s>k)

             {

                count++;                    

                i--;

                s=0;

           }

          }

        

      } 

    if(f==0) cout<<"-1"<<endl;

    else cout<<count<<endl;

            

}

return 0;

}

the break condition
else if(a>k)
{
temp=-1;
break;
}
you are using it along side taking the input array, suppose this condition is true and loop breaks before taking all elements in the array then these elements which you didn’t read will ruin you next testcase.
i suggest first read all input then perform any operation my code

when you are taking input array elements then at any time when a[i]>k then you are breaking out of loop which will not take all elements of array. just remove break statement and your solution is correct.

your modified code------

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

int main(){
long long int t;
cin>>t;

while(t–){

    long long int n,k,s=0;

long long int count=1,f=1;

cin>>n>>k;

long long int a[n];

for(int i=0;i<n;i++)

 {

     cin>>a[i];

     if(a[i]>k) {f=0;}

 }

 if(f==0) cout<<"-1"<<endl;

 else

{

  for(int i=0;i<n;i++)

  {

          s+=a[i];

        //cout<<"i is "<<i<<" s is "<<s<<" c is "<<c<<endl;

        if(s>k){

            count++;
            i--;
            s=0;
            }
  }

  cout<<count<<endl;

 }  //end of else condition

}

return 0;
}

I did count the last trip , that’s why I’m initializing count =1.
however, with some slight changes, this code ran but above one didn’t ,I don’t get why

#include

using namespace std;

int main()

{

int t; 

cin>>t;

while(t--)

{

    long long int n,k,s=0;

    long long int count=1,f=1; 

    cin>>n>>k; 

    long long int a[n];

    for(int i=0;i<n;i++) 

     { 

         cin>>a[i];

         

     } 

              

      for(int i=0;i<n;i++) 

      {

              if(a[i]>k) {f=0; break;}

          else 

          {

              s+=a[i];

             //cout<<"i is "<<i<<" s is "<<s<<" c is "<<c<<endl;

             if(s>k)

             {

                count++;                    

                i--;

                s=0;

           }

          }

        

      } 

    if(f==0) cout<<"-1"<<endl;

    else cout<<count<<endl;

            

}

return 0;

}

If one weight is greater than K ,then f=0 .
why should I get other elements when I know if one weight is great and can break loop to print -1.

Can anyone tell a tc where my program fails??I tried it for over 2 hours
#include
#define ll long long int
#define fe(i, a, b) for (long long int i = a; i <= b; i++)
#define fl(i, a, b) for (long long int i = a; i < b; i++)
#define mod 1000000007
#define el “\n”
#include <bits/stdc++.h>
using namespace std;

int main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin >> t;
while (t-- > 0)
{
    int n, k;
    cin >> n >> k;
    int a[n];
    fl(i, 0, n)
    {
        cin >>
            a[i];
    }
    bool check = false;
    int c = 0;
    fl(i, 0, n)
    {
        if (a[i] > k)
        {
            cout << -1 << el;
            check = true;
        }
    }
    if (check)
        continue;
    int sum = k;
    int i = 0;
    while (i < n)
    {
        if ((sum - a[i]) >= 0)
        {
            sum -= a[i];
            a[i] = 0;
            i++;
        }
        else
        {
            sum = k;
            c++;
        }
    }
    c++;
    cout << c << el;
}

return 0;

}

eg.
t=2
3 3
1 4 2
2 2
1 1

here for test case 1, when you are taking input 4 which is greater than k(3) then you are not taking further elements of array. here you will not take 2 in array.
so i think the 3rd element of first test case will be the N(size of array) of second test case. and in this way it will ruin all test case. its no use to consider elements after 4 for the answer but you must take all input according to question. hope now you understand.

Damn, now i understand .
Thank you very much

1 Like

In Setter’s solution, why is ans++ at last condition to sum>0? Won’t sum always be greater than 0 for the last trip since Wi>0? I incremented ans at last without the if condition and got WA.

1 Like

Better separate out the flag out of the logic loop, then break the current loop if flag is raised on account of box heavier than k.

Brother don’t worry your solution is correct just a little mistake. you forgot to put “break” statement after printing -1. assume a test cases has more than one element which is greater than k. then it will print -1 multiple time.
eg.
1
4 4
6 5 2 3
it will print -1 two time.

correct code–

#define ll long long int
#define fe(i, a, b) for (long long int i = a; i <= b; i++)
#define fl(i, a, b) for (long long int i = a; i < b; i++)
#define mod 1000000007
#include <bits/stdc++.h>
using namespace std;

int main(){

int t;

cin >> t;
while (t-- > 0)
{
int n, k;
cin >> n >> k;
int a[n];
fl(i, 0, n)
{
cin >>
a[i];
}
bool check = false;
int c = 0;
fl(i, 0, n)
{
if (a[i] > k)
{
cout << -1 << endl;
check = true;
break;
}
}
if (check)
continue;
int sum = k;
int i = 0;
while (i < n)
{
if ((sum - a[i]) >= 0)
{
sum -= a[i];
i++;
}
else
{
sum = k;
c++;
}
}

c++;
cout << c << endl;

}

return 0;
}

1 Like