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.)
My solution: CodeChef: Practical coding for everyone
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.
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:
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
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.
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.
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.
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.
