Wrong Test cases for Question "SERIES", of contest CODEMANIA

general
26

Totally missed that.

27

I totally agree that this was completely unfortunate for coders like you. The problem was relatively at the top with a lot of submissions when I read it. The first idea I got was “oh, it seems greedy should work” because these test cases are quite unintuitive. The samples passed, I submitted, got AC, moved to next problem without even realising the actual complexity of the problem.

28

Is this problem solvable for the given constraints, seems like if a greedy solution (correct) existed, then the problem would have already been asked somewhere till now.

30

Yeah you’re right, the answer would be “No” for those test cases.
I’m sorry I didn’t read the problem statement clearly i guess.

31

This is a very easy problem, if you guys want, I can clear everyone’s confusion once and for all.

Some points to take care:

  1. It asks for subsequence, so you should not change the order, like many have considered in their counter test cases.
    2)The author has mistakenly forgot to mention that numbers have to be different. (That version, demand increased time limit, (I have solved it)). Why I said that, the author forgot; because 1)if he intended for repeated version, he would have increased time limit, 2)the solution for distinct passes and gets AC.

So this proves, the author intended for distinct version, but forgot to mention in the question.

So, now we are left with distinct version and its very easy, if you guys want I can explain it for you.

And I would be happy if someone could create counter test-cases which break my code(following above constraints).

Thanks!

32

bro i upload the same post but then i figured out we have to divide array into 2 A.P i subsequence manner.
here ur 2 nd series 5 8 11 is not a subsequence.
hope this helps by the way i didn’t get the AC still :sweat_smile::sweat_smile:

34

Not the smallest ones I guess but , we can take the first 2 elements of the original array and use recursion to form the 2 required series…

AC code : CodeChef: Practical coding for everyone

Basically I first start the recursion assuming a[0] and a[1] are going to be in different AP series…
Then I recur once more assuming a[0] and a[1] are going to be in the same AP series…
And in the recursion function I keep on adding the next elements to one of the 2 APs with some extra conditions…

37

For n<= 4, answer is Yes.
From the first 3 elements at least 2 of them would belong to the same subsequence. So check for all the 3 cases by selecting any 2 of them and marking all the elements that belong to the AP formed by those 2 elements. Then check if the unmarked ones also form an AP or not. My solution