EGBOBRD - Editorial

PROBLEM LINK:

Practice
Contest

Author: Egor Bobyk
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu

DIFFICULTY:

Simple

PREREQUISITES:

implementation, basic maths

PROBLEM:

Some chefs go for a tour lasting N days. They take packages of bread for food. Each package has K pieces of breads. In i-th day, they eat A_i pieces of bread.
Each day the last piece of bread of an open package goes bad. Find minimum number of packages required to complete the tour.

EXPLANATION:

================
Let’s think step by step here.

  • Chefs should never leave more than one package open, since each night from each package one bread goes bad. So, it is intuitive.
  • From previous statement, we can also imply that Chefs will keep opening packages on a day until that day’s demand A_i is met. And, leave the remaining(if remaining) breads for the next day.
  • We can, in constant time, find the number of new packages to be opened if we know current(say extrm{cur}) and required(say extrm{req}) number of breads. We need to open x packages such that x*K + cur \ge req where x \ge 0. Now, we can easily define x as extrm{ceil}(\frac{req - cur}{K}) or basically in integer operations as
    (req - cur)/K + ((req - cur)%K > 0)
    Second term is required to satisfy the inequality.

This is our solution expressed as a pseudo code:

     N, K, A[] = input

     cur = 0     //total number of breads available right now
     ans = 0     //total number of packages opened till now

     for i = 0 to N - 1:
          //solve for inequality cur + x*K >= A* where x>=0
          x = (A*-cur)/K + ((A*-cur)%K > 0)
    
          //if x < 0, no package required
          x = 0

          //increase answer if packages opened
          ans += x

          //change current number of breads left after consumption
          cur = cur +x*K- A*

          //decrease 1 bread if some number of breads are left
          if (cur > 0)
              cur--

     print ans

COMPLEXITY:

For each test case, complexity is O(N) because we are traversing over number of days ie. N here.

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

Please help me out…I run this program but wrong answer Subtask1 task#0,Subtask2 task#3,Subtask3 task#7…
Can anyone please rectify my problem and please tell me the case where the code would not be applied (at which value of N,K and A*)…

  import java.util.*;
  class TryIt {
  public static void main(String[] args) {
     Scanner in=new Scanner(System.in);
     long T=in.nextLong();
     for(int i=0;i < T;i++){
         long N=in.nextLong();
         long K=in.nextLong();
         long sum=0,count=0,quo=0,ans=0;
             for(int x=0;x < N;x++){
                long A=in.nextLong();
                sum=sum+A;
                if((A%K==0)&&(x<(N-1))){
                    count++;
                }
            }
            ans=sum+(N-1)-(count);
            quo=ans/K;
            if(ans%K==0){
                System.out.println(quo);
            }
            else{
                System.out.println((quo+1));
            }
    }
}

}

why i got only 15 pts .Can somebody check my code plz…
#include

using namespace std;

int main()
{
int T;
long int N,K,pk=0;
long int *A,i,chk;
long int rem,divi,temp;
cin>>T;

    while(T--)
    {
        pk=0;
        temp=0;//it stores the pieces remaining after eating current day's need
        divi=0;
        rem=0;
        cin>>N>>K;
         A=new long int[N];
        
        for(i=0;i<N;i++)
            cin>>A*;
        for(i=0;i<N;i++)
            {
            
                if(A*-temp>0)//if the left over pieces are less than those to be eaten 
            {

             divi=(A*-temp)/K;
             rem=(A*-temp)%K;
             pk=pk+divi;

             if(rem!=0)//is there need of more packets 
                {pk=pk+1;

                temp=K-rem-1;//subtracting 1 bad piece
                }
                else//no left over pieces perfectly divisible
                    temp=0;
            }

            else//if the left over pieces are greater than those to be eaten 
            {
                if(i==N-1)//if its the last day then no need of extra pack
                break;
                else
                    if(temp==A*)//if the left over pieces equal the requirement
                    temp=0;
                else//if the left over pieces are still greater
                    temp=temp-A*-1;


            }

            }

    cout<<pk<<"

";
delete A;
}
return 0;
}

test case : 3 3 2 2 (i.e 4 days)
for K = 6
optimal order :–
3 from 1st packet, 3 from 2nd packet, 2 from 1st packet, 2 from 2nd packet, - total 2 packets opened

your soln:
post condition after each loop:–
i=0:
x = 1
ans =1
cur = 2

i = 1:
x = 1
ans = 2
cur = 4

i = 2:
x = 0
ans = 2
cur =1

i = 3:
x = 1
ans = 3
cur = 4

which gives the answer 3 which is actually wrong… are you sure it is greedy ??
Is it not flawed??
shouldn’t the approach be to minimize the no. of wasted breads??

Hey, I have a doubt w.r.t. test case 3 3 2 2 (i.e., 4 days) for K=6 (K being no. of breads in a package).

The answer should be 3 because as per the question, “Each day the last piece of bread of an open package goes bad”.

on 1st day: no. of packages used= 1, left out breads = 6 - 3 - 1 = 2; (-1 is because the bread goes bad)

on 2nd day: no. of packages used= 2, left out breads = 6 - (3 - 2) - 1 = 4; (-2 is yesterday’s left out breads)

on 3rd day: no. of packages used= 2, left out breads = 4 - 2 - 1 = 1; (4 is yesterday’s left out breads)

on 4th day: no. of packages used= 3, left out breads = 6 - (2 - 1) - 1 = 4; (in (2 - 1), -1 is yesterday’s left out breads)

Therefore, total no. of packages used = 3;
Please correct me if I am wrong. Thanks in advance.

1 Like

@gridhar_m yes you are right…i checked My AC soln and your concept too

suppose i open the first packet and take 3 breads and let the topmost bread remain there…
then the next day i take 3 breads from second packet and let the topmost bread remain there…
next day i remove the bad bread and also 2 breads from 1st packet.
and next day i remove the bad bread and also 2 breads from 2nd packet…

As only the piece that is exposed to mold is wasted only two packets must be used…

I don’t think that we will eat Ai bread and throw the next bread that is exposed then and there… it is pointless, as another piece of bread will be exposed(More wastage). it is only when we eat the next day or later in the tour that we throw the bad bread. And if only the last piece of bread is wasted then 3 3 2 2 should give 2 optimally.

The question is even if there is a last piece of bad bread, will the 2nd last piece also go bad…
Clarity of the question is questionable… :stuck_out_tongue:

I got only 15 pts. Can somebody check my code plz.

Atleast let me know the test cases that are failing. Thanks in advance.

I got 75 pts
And my only wrong answer is Sub-task 2 Task#3
Plz tell me which test case is my code not satisfying.

#include<stdio.h>
#include<math.h>
int main(void)
{short int T;
scanf("%hd",&T);
while(T>0)
{
int n,i;
scanf("%d",&n);
long long int k,j=0;
scanf("%lld",&k);
int a[n];
for(i=0;i<n;i++)
{
scanf("%d",&a*);
j+=a*;
if(a*%k!=0 && i!=n-1 && j%k!=0)
{j++;}

    }
    if(j%k==0)
    {printf("%lld

“,(j/k));}
else
{printf(”%lld
",(j/k+1));}
T–;
}
return 0;
}

They eat acc. to daily requirement. So go on adding the no of breads they eat daily AND add 1(bread that damages daily). Don’t add 1 bread if(sum%k==0), because on that day no bread will remain. THUS, print sum/k or (sum/k)+1
which gives total no of packets required for throught the trip. TOO SIMPLE :slight_smile:

SOLUTION: http://www.codechef.com/viewsolution/7440314

Why this code gave WA…Please help

Can anyone take a look at my submission.
https://www.codechef.com/viewsolution/8536505.
i am taking an array dp[] which contains the no of of packages opened after each day and another array left[] which contains no of left over breads after each day
i am getting just one WA in subtask 2.

Hey Thanks this is useful coding link… Thanks for sharing…

Netsuite Partners

@tejasvi96 this is because you have to use long long. check your code, http://www.codechef.com/viewsolution/7478446 , I just changed type to long long

thanx for the help avmnusng…

Please HELP HELP …Me out…I have tried most of the test cases…

Can we know the testcases used by judge please ?

Yes answer is 3.

Try this:
1
5 4
6 3 5 1 6

Answer should be 6. Your code gives 7.

Thank You Very much