You are not logged in. Please login at to post your questions!


Weak test cases of Chef and Subsequences (CHEFCODE)

See this accepted solution for 100 points: Link
See this accepted solution for 30 points: Link

Both the solution has worst case running time of O(2^n). The only difference in both solution is that one is handling counts of 1's in array separately, which in no means causes Optimization in general.This is just the case where you rightly guessed the one failed case of TLE.
Some stronger test cases should have been there in Larger subtask.

Test case for which above mentioned 100 points accepted solution will fail:
30 1000000000000000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

asked 19 May '17, 14:26

rohit_0801's gravatar image

accept rate: 10%

edited 19 May '17, 14:48

Yes testcases are very weak


answered 19 May '17, 14:41

hruday968's gravatar image

accept rate: 14%


answered 19 May '17, 15:38

dushsingh1995's gravatar image

accept rate: 10%


exactly..that is what I am trying to convey that the testcases for the 2nd subtask was very weak..the testcase which I mentioned was just an example to show that the code should not pass in given time constraint..

(19 May '17, 16:05) rohit_08013★

Not necessarily stronger, depends on the code

(19 May '17, 18:03) prakhariitd6★

@rohit_0801 we agree about solutions of order O(2^N) must not pass larger subtask. In my opinion, it is not hard to create such kind of datasets for this problem; seems even logic to add those cases... this is one of those times when unfortunately problem-setter and tester has done not enough work.


answered 19 May '17, 19:09

ymondelo20's gravatar image

accept rate: 5%


yes...that is what I am trying to say.Generally, the question at 6th number hardly crosses 1000 successful submissions.Might be many participants have used such kind of approach and got 100 points, which shouldn't have happened.

(19 May '17, 20:39) rohit_08013★

Update: Sorry, I missed the fact that numbers may not be distinct, and hence the below written comment is rendered useless.

I think this should also pass for O(2^n) because, for any 20 distinct positive numbers, the lowest product possible is 20!, this will exceed 10^18 and hence will exceed any value of K. So your recursion, won't go beyond O(2^20), given that you put check condition which ensures end of recursion if product exceeds K, which I think is enough to pass within given time limits.

This is mentioned in the editorial though.

But unfortunately, I do not understand why, does not pass if you do not seperate "ones" from the array!


answered 19 May '17, 14:42

lohit_97's gravatar image

accept rate: 2%

edited 19 May '17, 17:46

yupp right!! But the solution which i have mentioned above shouldn't have got 100 points in any case.Some strong cases must have been there to avoid such solutions to get passed.

(19 May '17, 14:47) rohit_08013★

@rohit_0801 , @lohit_97 : I have the impression that you guys are assuming that numbers in the sequence has to be necessarily different; that is not the case for this problem... so that solution of order O(2^n) should not pass, otherwise it is in fact not of order O(2^n) ...



answered 19 May '17, 15:33

ymondelo20's gravatar image

accept rate: 5%

edited 19 May '17, 15:34


Distinct or not..what I am trying to say that the above mentioned solution(100 points) should not have passed as it will fail for many testcases including the cases which have distinct n numbers or non-distinct numbers as mentioned by dushsingh1995

(19 May '17, 16:11) rohit_08013★

Yes. My bad, Numbers need not be different.:/ Taking back my comment :)

(19 May '17, 17:45) lohit_974★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 19 May '17, 14:26

question was seen: 593 times

last updated: 19 May '17, 20:39