You are not logged in. Please login at www.codechef.com to post your questions!

×

Unable to find bug in SRVRS simple solution

Hi everyone!

My solution for July challenge problem SRVRS gets "Wrong Answer" even with very simple approach - link. It generates all possible answers (vector o) and prints them from last server to first and from first CPU to last. Also I added some asserts trying to find the bug; the asserts check that all answers are different, server id and CPU id are correct, the result contains exactly Q responses. Moreover, if one line is commented, solution gets "Correct Answer" (link). The commented line in function "place" actually does not affect the answer, since it operates with variable which isn't used here (I used it for more complicated solution). Also the correctness of operation is checked too and local variable "ans" (which is returned by the function) is marked as "const".

Besides, the author of the problem said (via "Comments" section) that this code gets "Runtime Error" at "testing page" (Codechef online IDE?)

Usually such things are the result of undefined behaviour caused by some incorrect operation, but still can't find it. So, can anyone please help with the following?

  1. What is wrong with the "Wrong Answer" solution?
  2. How the commented line changed it go "Correct Answer"?
  3. Is it actually WA or RE? What result should be displayed for interactive problems in case of RE?

Any ideas?

asked 18 Jul '17, 20:58

ashmelev's gravatar image

7★ashmelev
935
accept rate: 0%

Same kind of thing was also happening with me.. -_- but Could not find any reason why that was happening with my code.. Will try to search in yours though..

(18 Jul '17, 22:50) kauts_kanu5★
1
  1. There is nothing wrong with the WA solution (it simply runs out of time due to the complete iteration).
  2. If you delete cores, you will need to iterate over a larger number of servers next time. Again, both are 'correct' (as in not wrong).
  3. The judge returns WA for this situation (lack of response from the contestant in the given amount of time).

I would like to take this chance and apologise for not catching this earlier. I am deeply sorry that you had this problem during the contest.

Note: check @meooow's comment

(19 Jul '17, 00:36) alexvaleanu4★
2

So, does such SPOJ interface behaviour affect all interactive problems? Will it be changed or we just have to keep in mind it (or it is better to add some notes for interactive problems)?

(19 Jul '17, 20:26) ashmelev7★

Hi @ashmelev, I faced this issue too. I used Java and not C++, but the reason is probably the same for both. As far as I understand from my own submissions, a slow solution gets a verdict of WA with execution time -1.00 sec, instead of a TLE. Your code is slow because the complexity of your code is $\mathcal{O}(N)$ per query. The ss vector is of size $N$ and you are using pop_back to empty the vectors which are elements of ss, but the loop keeps iterating over the emptied vectors for each query. Commenting the pop_back statement terminates the loop in the first iteration always, so it gets accepted.

Also, you may not have faced this yet, but a few times I got WA with some positive execution time for a submission that should have got RE. So in summary, the verdicts are not what they should be.

link

answered 19 Jul '17, 00:01

meooow's gravatar image

6★meooow ♦
7.1k718
accept rate: 48%

3

After quite a lot of intense debugging, I have come with the same conclusion. The judge interprets a lack of response (a TLE when it needs to read something from the contestant) as a WA (this is the way the Spoj's interface behaves).

I apologise for not making an official comment during the contest.

(19 Jul '17, 00:31) alexvaleanu4★

Yes, sometimes these servers dont give RE clearly. I was solving SPOJ GSS1 (segment tree problem) and declared array length as ~2 x10^5 instead of 4 x 10^5. Guess what? No runtime error, it went to undefined behaviour and it took me 2 days to debug (some1 else actually corrected that- i asked it on discuss after giving up) that i am getting RE due to less size. Cannot depend on judge to give correct judgement (RE or WA) atleast for C/C++

(19 Jul '17, 00:59) vijju123 ♦♦5★

Q2. Undefined behaviour is very weird. Random comments can also change behaviour of code. When i got a runtime error last time, just adding a comment in last line of code changed the output from 0 to 5. It is possible that the commented line does not affect your code by any means, and source of error is somewhere else.

Q3. C++ is soooo humble language, it wont trouble you with Runtime errors everytime. Instead it will just go on unstable undefined behaviour and give you heaps of WA, numerous enough to drown entire town. More formally said, do NOT depend on judge to correctly state that you got a RE or WA. Sometimes, accessing array out of bounds gave me undefined behaviour, while other times judge clearly said runtime error. I dont know why this happens, but thats how things go.

Q1. Looking at your code. BTW, to detect the faulty part, just try using "/ /" to comment parts of your code, and check output on dfferent compilers OR one output without comment, another with some comments. If both the outputs are same, means the commented part has the error. Use this to narrow down to few lines and find it (i cant take a look now, will try again later tho ^^)

link

answered 18 Jul '17, 23:19

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 18 Jul '17, 23:24

Surprisingly, there is no undefined behaviour here. I checked both @ashmelev's code and my own judge multiple times.

The comment affects the running time of the algorithm. There is no memory leak of any other anomaly. The 'issue' is with the judge's message response.

(19 Jul '17, 00:38) alexvaleanu4★

That explains why i got exact same output when i debugged it for first 25 minutes. I had a big "WTF" face and then put it off for morning thinking it must be something i am unable to grasp for now. (trust me, debugging tricky things at night can literally give headaches!!)

(19 Jul '17, 00:57) vijju123 ♦♦5★

Hey guys,

Same kind of thing was also happening with me.. These are my two solutions in which one got accepted but other did not, And difference between two is only that I commented some section of code which was not used at all and It worked..

  1. https://www.codechef.com/viewsolution/14466402
  2. https://www.codechef.com/viewsolution/14466345

You can see that I am solving queries in below part of code after comment(# asking for queries), which is same in both case. And In accepted solution I have just commented a function and some variables which I was not even using. But one solution was giving WA and one was giving AC. I implemented same kind of solution in c++ too but it was giving problems there too(WA some time and AC some time). Resulting I could not move my solution further.

can you guys @vijju123 @meoow @alexvaleanu help me to figure out why this was happening?

Btw, In both solutions I am just storing all computers a priority queue with timeToHire as key and returning topMost PC from queue, in this basic solutions.

link

answered 19 Jul '17, 02:48

kauts_kanu's gravatar image

5★kauts_kanu
1.1k110
accept rate: 19%

Sorry, i saw this post jsut now (when i was referring this link to some thread). Will look into it if you still need it.

(19 Jul '17, 21:24) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,718
×595
×21

question asked: 18 Jul '17, 20:58

question was seen: 426 times

last updated: 19 Jul '17, 21:24