rng_58's blog

What do you do if you get WA?
By rng_58, history, 9 years ago, In English

One day you came up with a brilliant solution during a contest, implemented it very carefully, and submitted it confidently. The verdict was ...... WA.

Probably most of you have experienced this sad situation. You can start debugging if you know the reason of WA, but what do you do otherwise? I frequently have trouble with this situation, so I'd like to ask your opinion. What should we do when we get WA?

Here are several possibilities:

1. Reread your code.

This is the simplest way of debugging. You may find some stupid typos.

2. Try various manual testcases.

Examples may not be very strong. Try some small tricky cases against your code.

3. Recheck the correctness of your algorithm.

Have you proved your solution? Is the proof correct?

4. Reread the statement.

You may have misunderstood the statement. Read it again to make sure that you understood the task correctly.

5. Stress-testing.

Write a straightforward solution, create lots of testcases by yourself, and compare both solutions. This is a very strong way to debug your solution, but time consuming.

6. Change the coder.

When you compete as a team, ask someone else to solve the problem instead.

7. Doubt the judge.

Judges are humans. They are not 100% correct.

8. Give up.

You may have other tasks to solve. Simply give up the current task and try something else.

  • Vote: I like it
  • +371
  • Vote: I do not like it

Comments Comments (45)
| Write comment?
»
9 years ago, # |
  Vote: I like it +66 Vote: I do not like it

6) Maybe instead of asking your teammate to write a code again it's better to ask him to read your code and try to find bugs there?

And it's also useful to think about some extreme cases such as n = 0 or something else.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -44 Vote: I do not like it

    your teammate will take ages to understand your code, so it's better idea if he coded it again :D

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    In ICPC we have done both in various situations. Sometimes using another teammate for Rubber duck debugging is enough, sometimes actually walking the other person through the code helps them discover a mistake you've made, and sometimes it's best and fastest to discard everything and have the other person implement the solution from scratch. I would say that the threshold between these is determined mostly by code length and by acceptance rate of the problem -- we would usually go for the "do it all again" plan in situations when everybody around us is getting AC on the problem and we can't see any issue with the current implementation.

    In fact, I've actually successfully used the approach in an individual contest once or twice -- I discarded the entire solution and just rewrote it from scratch, more carefully and possibly in a slightly different way.

    → Reply
»
9 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Thanks I will check this method in future!

→ Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I really like stress-testing

→ Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I think you could explain more about your first reason...

Maybe a list of usual typos that we should check them first...

→ Reply
»
9 years ago, # |
  Vote: I like it +39 Vote: I do not like it

1.5 Check for overflows!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +303 Vote: I do not like it

I'll add "write it again, differently". If you already had two ideas, maybe one of them involving more casework, then maybe you won't make a mistake in the other.

Also "check for mistakes which you tend to do". One of them is the already mentioned overflow.

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

My procedure is very similar to yours, though I fail at #4 a lot of times.

  • Checking my code is always the first thing I try.
  • If after a couple of minutes I can't find the bug, I start implementing print statements to check the various states of the variables and stuff.
  • If this doesn't resolve the issue either, I try some easy test cases to see if it gives WA. If it does, I use the print statements to see where it goes wrong.
  • If this fails too, I consider coding a brute force solution to check against.
  • At this point, if it's still giving WA, I usually give up, sometimes only to find out later that the WA was because I had misunderstood the problem statement. Those times are really frustrating.
→ Reply
»
9 years ago, # |
  Vote: I like it +226 Vote: I do not like it

I usually do this:

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +60 Vote: I do not like it

For team competitions, after you have tried standard procedures and failed to find a bug:

Explain your idea to teammate and then go through code line by line explaining it to him.

I would say this has very high success rate, usually other person will spot some corner cases or suspicious parts of code and ask you questions you haven't asked yourself. Also sometimes, while you are talking out your idea and code you will find errors yourself.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I find this very useful too. When I'm reading code by myself to debug, I tend to think my code does what I want it to do, but I see much clearly when I'm explaining it to someone.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +155 Vote: I do not like it

    I'll let you all in on a secret. There is a little trick that can make the "explain solution to a teammate" approach way more efficient. This is it:

    If you are the one listening, say to yourself that the other person is a complete idiot and that you don't believe a word they say.

    I shit you not.

    The point here is that it's really really easy to just let yourself be convinced. Your teammate is smart, the stuff they are saying makes sense, it's all too easy to just nod after each sentence and let them convince you that what they are saying is true. This is the default what will happen when you start listening to someone. There are two reasons why this is the default. First, it requires almost no effort on your side, so it's really easy to lose focus and slip into this mode of operation. And second, it feels good -- after all, you are agreeing with your friend, you have established a rapport. But that's not why you are there. Instead, you need to focus on finding the bug. And if you don't already have a lot of training and mental discipline, telling yourself "this person is dumb and I'm going to find the bug they made and laugh at them" will help you focus, and it will put you into the right mindset.

    "We may be friends outside the game, but right now I'm your enemy."

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      I use this trick sometimes. Recently I realized one downside it has: you can convince your teammate that his correct solution is wrong. I actually did it a couple of times.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        In ICPC World Finals, I convinced my teammate that his (correct) solution was wrong, only to realize it actually made perfect sense about 10 minutes later. But then I couldn't convince him to trust himself again u.u

        For reasons such as these going the full route of "he is an idiot" is not very productive for me. I'd say "you know he made a dumb mistake somewhere" is a better mindset.

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

If that happens in the beginning of the contest and the problem is rather easy, I will print the source code, ask my teammate to read the problem and the solution, then I will proceed to implementing the next problem in the queue. Happened several times.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    No one else codes the problems on your team? Or do you send it to someone else because you think they'll find the mistake faster?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Everyone does, I just type faster than others :) So first problem(s) are typically implemented by me, while my teammates can concentrate on looking for simple problems and solving them. Of course, that does not last long: a special problem can come up where one cannot describe his solution in several words and it'll be faster to implement solution himself; I need rest from coding too.

      So, the idea here is to send the program back to either its 'author' or that the problem is simple enough to be understandable from the code. If either is the case, we parallel coding of the next problem and 'debugging' of the previous one (by another pair of eyes, which is efficient); and if neither is the case, we know that the problem is not that simple and requires more careful thinking and discussion, which is less fortunate, but it still useful.

      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -40 Vote: I do not like it

If one of my teammates gets many WA during contest he will no longer be my teammate. Actually, I think he will no longer be anybody's teammate too, and will become afraid of Competitive Programming for all his life. That's how hard men sport works.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    If one of my teammates

    >implying

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      he probably meant one of the two following:

      1- proof by contradiction: If one of my teammates usually gets many WA during contests he wouldn't be my teammate

      2- If one of my teammates gets many WA during contest he will no longer be my teammate.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        And I answered

        >implying you'd ever have teammates with that attitude

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it -23 Vote: I do not like it

          Do you mean that someone will dare to refuse participating with me? Don't think so...

          → Reply
»
9 years ago, # |
  Vote: I like it +63 Vote: I do not like it

I don't mean to be a joking, but this technique really works: Rubber Duck Debugging

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Stress-testing is really a very powerful idea.

I have written a difficult (for me) program recently. After WA with the stress test I found a rare bug and a "minimal" (with 16 input parameters) test case after about 50-60k iterations.

→ Reply
»
9 years ago, # |
  Vote: I like it +172 Vote: I do not like it

when tourist gets WA, problem setters wonder if they have made any mistake

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

    True story.

    Usually, at least the first few submissions on each problem are examined manually by the judges. This way, if there is indeed a problem on the judges' side, they find it sooner rather than later, and may be able to fix it before it is too late.

    And it just so happens that the higher rated coders usually get the first few submissions on a problem...

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +146 Vote: I do not like it

    when tourist gets WA, he asks jury whether they are sure tests are correct (happened to me once :) )

    → Reply
»
9 years ago, # |
  Vote: I like it -25 Vote: I do not like it

You think that you have got WA in a problem that needs to get your answer mod MOD!

How to debug this codes? or better question is that " how to understand the bug is from main algorithm or it is just for not getting mod in some operations!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not hard to check if there are some operations where you forgot to get the modulo

    → Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

I didn't know there are 7 steps in between....

→ Reply
»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

The particular case of "1. Reread your code":

In my case, sometimes I recall past experiences to find the bugs. After solving thousands of problems, we'll be used to predicting which part is likely to cause bugs. For example, when I'm implementing Aho-Corasick, I often forget to mark the nodes which indicate the string whose suffix is a key. So when I use Aho-Corasick algorithm and get WA, I check this point. (Of course I also check other parts because this algorithm is difficult.) So the more problems you solve, the easier you can find where's wrong.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if I get WA in a problem I try first to revise my code to be sure that I have no stupid mistakes after that I try to hack my idea to make sure that it is true

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can we write to rng_58 and ask him for help? :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that falls under points 6. and 8. at the same time.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Totally re-writing the code sometimes helps.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Specially when there are many cases to handle, and you realize you forgot to handle some case in closely-related cases.

    → Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Doubting the judge is never a good idea for rookies like me. After WA ... "OMG!!! Judge is stupid! >_<" After contest.... "OMG!!! I am stupid ;_; " If you're less than yellow, absolutely never doubt the judge.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I do like that:

1.First of all i read the statement if i understood problem correctly.

2.If everything is ok with statement i reread the code for small bugs.

3.If there is nothing i rewrite the code.(This is important because sometimes is better to rewrite the code in ~10 minutes instead of debugging in ~30-60 minutes).

4.If this doesn't work then i delete all and begin to think in a complete different way.

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I always first check standings to see how many coders got AC between start of typing and my first submit.

→ Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

When there are recursions in your C/C++ code, please check whether you wrongly use a static variable instead of a ordinary variable, for example:

//......
int a[maxn + 5];
//......
void dfs()
{
//......
static int tmp[maxn + 5];
memcpy(tmp, a, sizeof tmp);
dfs()
memcpy(a, tmp, sizeof a);
//......
}
//......

It's really confusing sometimes, and when you unluckily encounter this mistake, you might spend hours on it. Both I and tgopknight have suffered from this mistake and we all spend lots of time finding it :(

BTW, it is often the case that you can't pass the examples instead of getting WA. But I think this is still a good piece of advice :)

→ Reply