How do you guys find why you are getting the wrong answer?

1

I have been facing this problem where I am not able to figure out why am I getting the wrong answer, how do you guys fix your program?
I give in my different inputs, but this takes a lot of time and will not yield good results and not help with debugging.

3 Likes
2
  1. understand what your question is exactly asking.
  2. wrote the code but wrong answer pops up. so time to find the mistake . sit back
    and think of some edge cases where ur code can fail . check it.
  3. still not finding bug. Insert few print statements and check values of some
    important variables in your test cases. see whether they are printing all those value
    which you expected or not.
    4.if still not getting the bug then take help of your friends ask them or watch tutorials of those question where they discuss the solution , they will tell you important edge cases of those question.
  4. Dont waste more than 1 hour on one question . if you feel you are very close to correct answer then you can give more time.
    6.Ask your doubts here for any question.
4 Likes
3

Get involved. Live the question. Understand the problem inside out, and ask for clarifications if some things seem ambiguous: I think this is the most important task (subtask 0 if you may :stuck_out_tongue:) in solving any problem. Don’t miss any detail, read the problem a thousand times if it takes but make sure you understand just about everything there is to.

Now that you have a proper understanding of what you are asked, you need to find a way to get it done. Most questions, with enough practice, are solved within minutes at this point (provided that the understanding is not flawed). Others require effort on your side, and you must decide if you can or not. If you can, you yourself will make sure that you don’t give up before the problem does. And believe me, it always does! Sit back and think a little about the problem, make a picture around it in your mind if necessary (sometimes, a good thought experiment makes you reach the solution faster). Work on your initial ideas and follow where they take you. Sometimes, you will reach a dead-end but because you were involved, you’ll start getting newer ideas so keep following them to their ends until you find the one. It might happen at times that you’ll feel skeptical about an idea but don’t drop them: once you start trusting even your weirdest ideas in complete confidence, then you’ll start loving the process and not get bored (getting bored stimulates giving up sometimes too).

It’s been quite a while, but now you feel confident in an idea. Now it’s time to express! Remember, do not bother about the implementation in the second step, just focus on getting a solution: implementation is secondary (yet still, the only concrete thing). I used to get affected earlier if this idea can even be implemented. Then I started challenging myself at it, getting the most complicated ideas expressed in code. It starts happening shortly with practice, to the point that you don’t even worry about it, feeling like you can code almost any idea you can think. Hence, I advised earlier about keeping these two independent. Anyway, you finally coded the solution. Now comes the last (and the deciding) task: debugging.

See, being good at this also comes from practice. In terms of practice, it demands the most of all steps listed. In exchange, it contributes to your learning the most too. So you have to be patient is all. A side of you has understood the problem and solved it. Now it’s time to keep that side at the side and make the code a battleground for experiments. Keep throwing all kind of test cases you can think of, and show no mercy. If you feel it passes all of them, try submitting. If it fails, you can see what’s wrong. It’s a good thing they show you what kind of error occurs, so the bugs have a finite space to breathe in. You continue, and you continue, and you continue… you feel some level of frustration but you continue nevertheless. You reiterate over all the steps, in an attempt to not miss even the slightest point of error. And then it happens, a ray of light. Something, anything, every time in a new disguise (a silly error, something devastating, or something entirely different) but the thing is: it does happen if you are patient. In almost every previous submission, there was some part of you that was not satisfied completely. But now every part is in sync and they all know that it’s finally done and they all wait for what they have all this time: that f***ing green screen! The satisfaction is more than the length of this answer, it’s otherworldly.

In the end, there will be times when you see things getting compromised, people stealing solutions to get ahead, and it’ll seem tempting. But remember, nothing beats the satisfaction of this process. And given time, you’ll get addicted to it. You won’t even think of it as a process, it will become a reflex and multiple steps will merge into one (example, solving and implementing simultaneously). Okay, endnote :blush:

25 Likes
4

Just try to solve all the given testcases, on pen and paper and try to think what could be worse input. This will help you in understanding what the problem is actually asking for.
Don’t worry, with experience you will get better in it.

And I’m thankful to you that you didn’t asked “how do you guys deal with TLE”.

3 Likes
5

Well, I just put some extra printing lines in the code to check where my code is giving an unexpected output .

6

The real answer apart from motivational talks is… Stress Testing your solution

2 Likes
7

stress testing works quite well with most problems.

8

It looks like you write on Quora :joy:

2 Likes
9

First of all, thank you for answering, and one more question from your answer. You speak of “worst input”? Can you elaborate on that? I can give you the question I am working on and you can explain me with reference to that.

Question : FROGV Problem - CodeChef

10

Thank you, I will look this up

11

Thank you for answering

12

worst-case input refers to an input that an/your algorithm is likely to struggle with.
In general these are the large test cases, because for those an algorithm takes the longest to solve those. But as we are speaking about correctness instead of time complexity these are harder to find. It most often comes down to experience. By having made mistakes before you more easily recognize those mistakes.

By looking at your code I can see a couple mistakes you made.

Issue 1

frogs array is 0-indexed; input is 1-indexed. I find it odd that 1-indexed input remains the trend in programming competitions.

Issue 2

The sort breaks the indexing. For the example input when they query 1 3 you are actually answering 1 4 because the 5 at position 4 was sorted to position 3. These happen to give the same answer. This issue is a little harder to solve; I will leave it as your challenge for now.

Issue 3

You’ll stumble across this issue :slight_smile:, so I’m not going to elaborate more.

1 Like
13

Yeah, the answer does seem like something on Quora. I didn’t intend to sound motivational, but it turns out to be more poetic than technical. Anyway, stress testing is the word as others pointed out. One might randomly generate a set of test cases (with constrained distributions if it takes) and test the two outputs (the other from the brute force) with any difference checker. It works most of the time if nothing else does :slightly_smiling_face:

1 Like
14

Here’s what I like to do when I get the wrong answer.

  1. Check my code on some trivial corner cases which are easy to think about.
  2. Check the constraints given in the question to see if I missed any corner case.
  3. Read my whole code line by line or the code which I think is most susceptible to errors and match it with my initial idea to make sure I didn’t do any implementation mistakes or left any corner cases.
  4. If I am fairly sure that there are no implementation mistakes, I think about the idea of my solution carefully and see if the idea itself is flawed for any test case.
  5. Think of trickier test cases.
  6. If possible, write a brute force program and a random test case generator and a program to match my original program’s output with a brute force program on a lot of random test cases and let the program run for a couple of seconds or minutes.
  7. If brute force is not possible or it doesn’t work in finding the desired test case, there is most likely some mistake with my approach. So try thinking harder why it is not right and if I can’t think of why its not right, I might try to approach the problem with a completely or significantly different approach.

Some common implementation mistakes to look for that I can think about are-

  1. Integer overflow
  2. Precision error in case of floating-point numbers.
  3. Not initializing a variable with the required value.
  4. OBOB (Off by one bug): When a loop runs on one less or one extra value.
  5. Using wrong variables in wrong places like using the variable ‘i’ in a loop while you have used ‘i’ somewhere else or using ‘i’ in a nested loop of ‘i’ or reusing of other variables which are not meant to be reused.
5 Likes
15

In this video Errichto has explained how you can test your code in case you are not able to find corner cases where your program is failing…

2 Likes
16

For this question you can think of Disjoint-Union data structure, i.e. just assign a value “level” to each frog , such that all frogs which can send message to each other should be on same level. Now while answering the query you just need to check whether the frogs are on same level or not.

Worse case could be:

  1. Is it possible that two frogs are one same level, but still they can’t send message to each other.
  2. Is it possible that two frogs are different level, but still they can share message.
17

My approach to this program was that the distance between the (i+1)th frog- i th frog should be less than k, which is the distance that is inputed by the user. I found one error yesterday, but the question has not been accepted still.

18

Well hello again, it has been a while and I am still doing something wrong. I am linking you the most recent upload of my solution. I am still getting wrong answer. Maybe you can look into it and point out what I am doing wrong? Thank you.

https://www.codechef.com/viewsolution/34519236

19

Tips to get rid of WA, TLE, RTE:
● Use well structured algorithm for solving problems. Before writing code you should have all the edge cases crucial steps in your mind. So that it doesn’t fail on their judging servers.
● Don’t write code based on your intuitions, if you can proof your solution like; it will definitely work then only you should proceed to write code. This helps a lot. Learn proof techniques for correctness of algorithms
● Test your code on atleast 5 test cases. This 5 testcases are different from from your input-output examples. Find answers to these test cases by hand, and check your code on these testcases. If it matches with your answers, then only you submit your code to online judge. These testcases can be random but try to generate some test cases which cover edge cases and are tricky.
● Try to write clean, concise and small codes these helps in finding bugs. use functions in your code to short a block of your program. Use proper spacing and indentation, this helps identifying which statement belongs to which block. Take a look how International, Grandmasters code.
● Some common causes for WA are int overflow, missing initialization in each testcase for some variables.
● RTE(RunTimeError) can also be treated as WA. Make sure you are not dividing with 0, not accessing an array element which is beyond size, poping an empty stack, in some loop int exceeds its limit these results in infinite loop, not giving break statement for while loop, too much depth in recursion.
● Again as the saying goes “Practice makes a man perfect”. practice is the key to all your questions and failure.

20

This is beautiful! Thank you so much.