Chef and Line COOK91

Link to question : CodeChef: Practical coding for everyone

Test case:

1

5 1 1

0 0 0 0 0

Please explain why answer for the above test case will be 1?

(y = x+1 ,as all element of array are 0 ,so a[i]>=1 not possible.)

Here is my solution : Competitive-Coding/CodeChef_Chef_and_Line.cpp at master · DollarAkshay/Competitive-Coding · GitHub

Take that and see what the output will be for any testcase.

I think it should be 0 for your example

How can a sub sequence will have 0 elements? The question said that, a element is inside good sub sequence follow rules such that A_i > A_{i-1}*K+b. But if the sub-sequence is empty, then you will have to place any one element by default/trivially/vacuous proof

Updated the question.

" But if the sub-sequence is empty, then you will have to place any one element by default/trivially/vacuous proof"

why?

Didn’t get this part?

Yeah this thing caused me 2 wa,probably th reason is that in question it is given “For each valid i ,Bi+1 should be reachable from Bi(if Bi+1 exists)”,here they are talking for each element Bi and not Bi+1,so if there is 1 elememt,then Bi+1 doesnt exist so we dont have to check that greater conditon.

1 Like

Probably most of the submissions was saved from wa,since they used greedy in which they actually initialized res with 1 (I dont know if most of them actually thought abt case k=0),however for one who solved with dp ,(taking separate cases)it was a pain

I was confused by fact that if one element exsits then how will B(i+1) condition be satisfied and got 6 WA due this.

Theres nothing to be confused here, sadly. You will encounter such questions a lot , especially in important contests like ICPC. Check out Beautiful Arrays question, it uses the same concept. If environment is as such you cannot apply the conditions on the incoming elements (eg- due to no 2nd element to compare in this case), then the element is trivially passed the tests.