CHFRAN: Bad test cases- Wrong solution got 100 pts

This might sound like a cringy schoolboy going to the teacher with his classmate’s copy to get his marks deducted.

Hi,

Yesterday I asked a question in this forum regarding not being able to find a mistake in my CHFRAN python code that got 90 pts in the contest but my question got no answer. Today I picked up a random contestant’s python solution, created a test file with random inputs (as per problem constraints) and compared his outputs to mine. I found that the test cases of the problem are so bad that 5 out of 20 test cases I created in the first try proved that his solution was definitely wrong. And I have still not been able to find the error in my solution (I’m not saying mine can’t be wrong, but doesn’t seem like it.)

@rishup_nitdgp: Please take a look.

My solution: https://www.codechef.com/viewsolution/28300857
I have just created partitions of the set of ranges based on overlap and keep track of the number of active (open) ranges which have not ended yet. Also keeping track of the previous_active and previous_to_previous_active values.
This helps to find the local (as well as global) minima of the active variable.

His solution: https://www.codechef.com/viewsolution/28142465

A few test cases for which his solution gives wrong answer (ideone link: https://ideone.com/2uRXmt -all 5 test cases give zero when run against his code).

1 Like

Well, you’re in good company: weak testcases are one of my pet hates (though I recognise how hard it is to create strong ones!), and I’ve reported Problems for this several times in the past :). Allegedly, the Problem Setter is actually officially responsible for improving the testcases in such a situation:

(from here).

I still maintain that there should always be a Test File which consists of tons (i.e. - in the hundreds or thousands) of small, randomly-generated testcases - these almost always flush out incorrect solutions like this. CHFRAN already has 15 Test Files - what’s the harm of one extra one? Even a suboptimal solution should blast through such a Test File very quickly, so the additional strain on the SPOJ servers should be minimal.

I’m going to be adding such a Test File to any of my Problems :slight_smile:

6 Likes

Thanks for your response. I totally agree with your proposal.

Also could you please help me find the bug in my code? Why just 1 test file in the first subtask keeps failing? I’d really appreciate it. Thanks!

1 Like

I haven’t looked at CHFRAN yet and it looks non-trivial, so I’m not the best person to ask :slight_smile:

Bro why do u think 0 is wrong answer for first of ur testcase.Since (23,30) is exclusive of rest ranges,we can easily group them in two subsets without the need to remove any range.

1 Like

Bro just check whether you understand the problem the same way as I do. My understanding is that out of the following 4 ranges, 3 partitions based on overlap can be formed:
54 77
79 84
23 30
78 81

(i) [23,30]
(ii) [54,77]
(iii) [78,81] and [79,84]

Clearly the answer should be that 1 deletion is required here in order to create two non-overlapping partitions.

Bro in the question it is not stated that all ranges in a subset should have common point.It is only stated that whenever two ranges have a common point, they are in the same subset.

And the answer to all 5 test cases is indeed 0. In all these test cases we either get a very small range like 23 - 30 or one like 95 - 98 which coincide with no other ranges and hence two sets can be easily formed. Your solution might be restricting you from placing disjoint ranges in a set which is possible if you go by the problem statement, that’s the best I can guess as of now.

1 Like

Well then the test cases are so bad that my bad understanding of the problem statement still got me 90 pts.

You’re right with your explanation. Well in that case, the test cases are so bad that my bad understanding of the problem statement got me 90 pts.

Yeah i agree

Hey @ritam777,

Your solution is not wrong as you misunderstood the problem that’s why you solve a superset of the given problem. Although, I didn’t include test cases that have more than 3 disjoint groups, sorry for this and also, I didn’t think that somebody misunderstood the problem this badly.

Why didn’t you answer my comment during the contest? It would’ve saved me some time trying to figure out what I asked about.

Many people had this doubt during contest. I think one comment about this was made public.
I agree statement was bit weak but you could have read comments section.

Bro forget how bad I am. Because my mistakes don’t affect anyone on Codechef but your mistake can waste the time of thousands of contestants.