You are not logged in. Please login at www.codechef.com 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, 14:26

rohit_0801's gravatar image

5★rohit_0801
2359
accept rate: 6%

edited 19 May, 14:48


Yes testcases are very weak

link

answered 19 May, 14:41

hruday968's gravatar image

5★hruday968
1.4k8
accept rate: 13%

link

answered 19 May, 15:38

dushsingh1995's gravatar image

4★dushsingh1995
6328
accept rate: 13%

1

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, 16:05) rohit_08015★

Not necessarily stronger, depends on the code

(19 May, 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.

link

answered 19 May, 19:09

ymondelo20's gravatar image

4★ymondelo20
2857
accept rate: 5%

2

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, 20:39) rohit_08015★

@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) ...

Regards

link

answered 19 May, 15:33

ymondelo20's gravatar image

4★ymondelo20
2857
accept rate: 5%

edited 19 May, 15:34

1

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, 16:11) rohit_08015★

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

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

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×164

question asked: 19 May, 14:26

question was seen: 452 times

last updated: 19 May, 20:39