Is it black magic or what?

http://www.codechef.com/viewsolution/3786033

Please somebody explain this to me.
This code is giving AC and it is just printing “-2.000000000”(without quotes).

It was just a matter of coincidence I and my friend discovered that there was loop hole in the system checker, could it have been possible that it might have happened in some past contests also?
If there is any probability of it happening before, then there is something seriously wrong with the system checker. @admin please look into the matter seriously.

15 Likes

@admin @vinayak garg @gerald have a look at this.

1 Like

It looks like the all test cases for the problem have the answer as -2.00 only. But the biggest shock is how @sikander_nsit deduced that all test cases have answer as -2!! (maybe Black Magic :D). If people come to know of such things then the question completely loses its meaning as very few will take time to solve it. Hope they add stronger test cases later.

@kostya_by @admin Please add test cases !!

1 Like

@kcahdog I have commented about this weak checker in the editorial . The problem is not with -2 actually any negative values are giving AC. The checker is not handling the negative values properly

3 Likes

Actually the original solution has been submitted by @sjsupersumit during the contest. This is his solution.

http://www.codechef.com/viewsolution/3784470

After the contest, I was looking at random solutions when I found this one.
So I ran it on ideone and saw that it was giving “-2.00000” for every test case.

6 Likes

Hi @all,

I haven’t attended the contest, but, I’ve read the editorial for TCP problem and it seems to involve numerical methods for integration/function approximation(and/or generation) by polynomial curves so that numerical methods can be employed.

In general, it’s quite hard to perform interpolations correctly, and, even if we are given the sufficient number of points (if we have a polynomial of degree N, we need N+1 points.), slight changes in the function coefficients might affect the overall area estimation (this is known I believe to be something along the lines of numerical stability or something alike).

So, possibly outputting negative values is enough for the judge due to precision being very close to 0 (10^(-10) is very, very small.).

The only problem I had seen before which slightly involved numerical methods was this one. But, in the end, it turned out a simple greedy method worked…

So, to wrap this up, it seems that while the problem was awesome in its own right and it presented a great application of numerical methods to competition programming/real life scenarios, it’s also hard to ensure correction of test data on such problems, but, nontheless, I got quite inspired by this problem to maybe write something similar in a future contest :smiley:

Best regards,

Bruno

2 Likes

I didn’t understand your reasoning about the precision… When program prints -2.00 and expected result is 173.75 it’s not really close enough…

5 Likes

I know, but I meant it for the judge internally… Maybe it gets “confused” with negative values when required precision is so close to 0, i.e. it might affect the judge itself… At least, the most precision I had seen had been 10^-6…

If you do write something similar in a future contest make sure the judge doesn’t get “confused”… Mistakes like this are not acceptable. Even if a problem is “inspiring” and “awesome”, generating and evaluating reasonably good test cases should be top priority.

I think that something bad (and unexpected happend), as @gerald wrote:

I’ve submitted a lot of wrong solutions during the testing phase, some of them outputs negative values and didn’t get AC. May be that’s bacause of some wrong positive values. Anyway I will check checker.

on editorial page.

1 Like

My bad, didn’t see that, thanks…

This problem seems to have been rejudged, because with the link you provide, i clearly see WA in the header :

CodeChef submission 3786033 (C++ 4.8.1) plaintext list. Status: WA, problem TCP, contest . By sikander_nsit (sikander_nsit), 2014-04-21 01:55:40.

Edit (yep, rejudged) :

The judge has been fixed and the
submissions in practice section have
been rejudged. The error occurred
because I assumed that in the judge -
first file was correct file and the
second file was the user output. Turns
out I was wrong.