Can anyone explain me the question from lunchtime?

here is the problem link :- https://www.codechef.com/LTIME79B/problems/STUPMACH

the problem was easy as lot of submissions were made but i totally didn’t understood i did the 3rd one but what we need to do in this i didn’t got . any type of help is appreciated.

1 Like

If at any index i, if you can keep a[i] things then for all i+1 you can only keep less than or equal to a[i]

Here’s a small code snippet

int limit=INF;
int res=0
for(int i=0;i<n;i++){
       lim=min(lim,a[i]);
       res+=lim;
}
cout << res << endl;

bro i am not about logic for answer i am asking what is the question asking us to do. what i understood that we need to find the maximum no of tokens that can be stored in boxes ,but if you find total sum of capacity of boxes it gives WA ,which shows approach is wrong

Wait. Are you adding the capacity of all boxes?

I think you should re read the problem first

1 Like

another thing what i understood we choose the L=N at the beginning and loop it down to 1 and in each loop according to value of L,all values from 1,2…are decreases .we ignore or leave cases when value at a index equals to 0.

Um…okay from what i can make out, you’re choosing the last box and adding token till box 1? Is it so?

Hi Bro,
basically you are given N boxes with different capacities like in eg 3 boxed with capacity 2 1 and 3.
Now your job is fill them and the way is to choose any box L and add one token and whichever box you choose you’ll have to add one token to all the boxes before it as well now you have to fill max possible tokens without overfilling any box in eg we chose L=3 now box 1 has capacity = -2-1, box 2 = 1-1 and box 3 = 3-1.
Box 2 is filled so we cannot choose 2 or any box after that so box one is chosen again total tokens = 3+1 =4.
Hope it helps!

1 Like

yep here is what i am doing is

 int L,c=0,tot=0;
for(i=N;i>=1;--i)
{
L=i;
for(j=1;c<=L;++j)
{
  if(A[j]!=0)          //if value at that index is greater than 0
{
A[j]--;               //decreasing value by 1
c++;                    //incrementing 'c' so that when c>L loop breaks
tot++;               //counting capacity
}
else
{
continue;
}
}

First box will always be filled completely because there is no box behind it and if next box is greater than it then it will also be filled do you understand why?

2 Likes

we are distributing tokens 1 at a time to any index

To that index and all the indices before it.

2 Likes

ok that i was not catching up . i was distributing token in way for example L=3 i will distribute 3 tokens ,for l=2 i will distribute 2 tokens …that was misktake L is index upto which we need to distribute.thank you bro

1 Like

Can you explain the problem, if you understand?

yes bro in this question we are given ‘n’ boxes and capacity of those boxes is given. we choose any index ‘L’ and from start to that index (from 1 to ‘L’) we put 1 token in each box.if capacity of any box is filled we choose index of box before that which is not full.

let us understand with example clearly

you are given 3 boxe or ‘n’=3
capacity of boxes is 2 ,1 and 3
we choose any index between 1 and 3 ,i start ‘L’ from 3(last index) because i can put 1 token in each box upto index 3(last index) .

now capacity of of boxes is 1,0,2 ,we will use one variable to count total tokens uses
here total 3 tokens used 1 in each box so tot=3;
as we can see at 2nd index value becomes 0 ,now we cannot choose any index greater than equal to 2 .

so we will choose index L=1 as it is non zero and now tokens capacity is
0,0,2 and tot=3+1=4
now we can’t choose any index greater than equal to 1 so we got our answer that is 4

Thank you very much bro for giving me your precious time, Now I understand the problem.

1 Like

I made a post covering all the questions from div 2 of lunchtime
https://discuss.codechef.com/t/december-lunchtime-solutions/48129/4