LTIME75 : Same Code Different Results

LTIME75 had some server issues lately, but regardless, it doesn’t explain this outcome. Here are two IDENTICAL submissions in the span of 1 minute during the last 2 minutes of the contest.
Solution 1 (WA) : https://www.codechef.com/viewsolution/26187936
Solution 2 (AC) : https://www.codechef.com/viewsolution/26188072

Had it even been TLE/RTE instead of AC, It would have been possible that due to server load, it gave different runtime verdicts. But AC and WA cannot be explained except if the Test Cases were changed DURING THE LAST MINUTE which seems ridiculous. Hence this is sort of a bug report and also a Far Cry for help coz I had accidentally submitted that same solution in a hurry to get it submitted within time and had I only submitted the first solution, I was sure to get a much higher rank and a negative delta rating change :stuck_out_tongue: . @admin Please look into this matter if possible

Looks like there is some undefined behaviour in your code. Submitting it multiple times yields different answers.

In particular for the input:
2
10 10 10 -6 9
2 24979445
-1 623690081
-7 476190629
-1 211047202
-10 628894325
10 822804784
-5 430302156
5 161735902
-8 923078537
-3 189330739
10 10 1 -10 6
7 317063340
-4 773361868
0 650287940
-8 462224593
-7 384836991
-5 576823355
-2 404011431
1 954291757
5 155374934
-3 164163676

it gives the output
24979445 24979445 24979445 24979445 24979445 24979445 24979445 189330739 189330739 189330739
5 5 5 5 5 5 5 5 5 5
sometimes, and the correct output:
24979445 24979445 24979445 24979445 24979445 24979445 24979445 189330739 189330739 189330739
155374934 155374934 155374934 155374934 155374934 155374934 155374934 155374934 155374934 155374934
sometimes.

Check it locally.

4 Likes

As @admin says, there is UB in your code.

Specifically, you’ll get an out-of-bounds access with your code with the sample testcase on the following line:

            int temp = cc[mid];

The UB was most probably due to setting high=n. Now on setting high=n-1, the code gives a complete WA, atleast earlier it was giving partial AC 30 pts. Any insights on where the bug might be. Thanks in advance.

Updated Solution Link : https://www.codechef.com/viewsolution/26194971

Have you tried to debug it? It fails for the sample testcase, so you’ve got a nice, 100% reproducible testcase :slight_smile:

As a hint: you should be getting -1 for the last two values in the sample testcase, but you are not. Maybe look at the values of a and b you’re getting, here?

Edit:

Oh - this thread’s really old, and only got bumped to the top because you fixed a typo :smiley:

3 Likes