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
4 Likes
Yes testcases are very weak
2 Likes
@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
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…
1 Like
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
1 Like
Yes. My bad, Numbers need not be different.
Taking back my comment 
Not necessarily stronger, depends on the code
@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.
1 Like
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.
2 Likes