robot-dreams's blog

Silly and preventable causes of WA
By robot-dreams, history, 6 years ago, In English

I don't think anybody likes getting WA. It's especially annoying when they're silly issues that are easy to prevent in the future, so I decided to keep start keeping track of things that have caused me to get WA. Here are a few:

  • Not setting precision high enough when using cout to print floating point answers

    • The default precision is only 6 digits, and problems often ask for more precision than that, so I think it's a good idea to do cout << setprecision(12) whenever floating points are involved

  • Using 1 << k instead of 1LL << k when the result won't fit in 32 bits

  • Only considering one direction of an undirected graph when reading input

  • Using the wrong priority queue ordering

    • Since C++ priority queues give you the max element by default, you need to initialize with priority_queue<T, vector<T>, greater<T>> if you want to get the min (e.g. in Dijkstra's algorithm)

  • Using the wrong parameter (e.g. n instead of m) when reading input(!)

    • I'm not joking, this has caused me to pass pretests but fail system tests before :(

What about you, what are some of the (silly and easily preventable) causes of WA that you've encountered?

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

Comments Comments (42)
| Write comment?
»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

I often get WAs on problems with multiple test cases because of

  • Not initialising arrays or clearing containers.
  • Not doing cout << endl; after end of output for a test case.
→ Reply
»
6 years ago, # |
  Vote: I like it +73 Vote: I do not like it

Reading n edges instead of n-1 edges when dealing with a tree.

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

Not using int64_t or long long when the some variable can be more than 32 bits

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

Using doubles when it's possible to use long long entirely

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

Though non-preventable, the prime cause of WA is trying to solve problems. :P

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

    It actually is quite preventable — just don't submit solutions. Yeah, I know, cheesy joke, but you are the one who started and I couldn't contain myself :)

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

Whiskey

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

missing the update of mid in binary search :

while(r  -  l > 1)

{

if(check(mid))l = mid;

else r = mid;

this part // mid = (l + r) / 2

}

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

    Why not write it on the top for maintaining convenience? Moreover, I think this kind of implementation is easier:

    	int l = 1, r = MX, best = -1;
	while (r - l >= 0) {
		int mid = (l + r) >> 1;
		if (check(mid) == 1) {
			l = mid + 1, best = mid;
		} else {
			r = mid - 1;
		}
	}
	/// now best is our answer
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      there is not too much difference between your and mine implementation

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

        The difference is you forget to update mid and I don't :)

        I think initializing the value of mid outside of the binary search is meaningless. You can do it in the loop if you write it on the top and it seems more convenient to me (well, at least to me, everyone has his/her own coding style :)).

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

not printing the answer ;p

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

Mixing up loop variables. I do this quite often:

for(i=0;i<n;i++)
{
 // lots of code
 for(i=0;i<x;i++);
}
→ Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

forgetting to comment out the output used for debugging lol

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

    Language called D has nice feature — you can put debugging output in "debug" clause and it will only be parsed when you pass "-debug" flag to compiler. So I can freely write everything I like and don't care about erasing it before submitting. Syntax is pretty similar to C++, so it's not as hard to give it a try. You can check my solutions or even better — solutions from user Gassa. He is red coder using D.

    That was one of the reasons why I started writing in D.

    Here Gassa has a nice article on D:

    http://codeforces.me/blog/entry/60890

    Or you can probably just write a lot of garbage, then put it in every solution to get something similar in C++.

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

    I'm a g++ user and usually use as follows:

    #ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

    When I compile it locally, I add -DLOCAL_DEBUG to the compile option and all the DEBUG() input is enabled. I don't need to remove the debug line when I submit because the whole expression inside DEBUG and DEBUG itself are substituted to nothing.

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

I used to get WA due to the debug statements but now I use template code for TRACE using cerr instead of cout so there's that

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

Using for (int i = 0; i <= s.size() — 1; i++) instead of for (int i = 0; i < s.size(); i++)

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

Thanks to operator precedence I constantly got WA for typing something such as if (a & b == c) (while I was thinking of whether the value of (a & b) equals c)...

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

Our team has made a special list of possible reasons of getting wa: link (in russian)

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

    bool f(); returns bool is my favourite one

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

I have been a victim of first one too many times and want to tell you are still wrong. Consider a case where answer can be as huge as 1e18.

Example
Output
Correct way
→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

  • Forgot to write a piece of code that handles special cases.

  • Used n instead of m and something like that.

  • Forgot to add ans %= mod somewhere, getting an integer overflow.

  • And the worst one: when you idea is based on some wrong assumption, and after writing many lines of code and getting WA you realize it fails and you have to rewrite everything ;(

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it 
for(int i=0;i*i<n;i++)
{
    ...
}

In case n is very large

→ Reply
»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it 
for (int i = 2; i*i < n; i++) {

instead of 

for (int i = 2; i*i <= n; i++) {

when dealing with divisors and primes and factorization

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

    And when n is large forgetting to write 1LL*i*i :(

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

Actually I can list a lot more

  • Forgetting a corner case.
  • Forgetting two corner cases.
  • Handling a corner case wrong.
  • Handling a corner case that's actually not a corner case, and is still correct in the general case.
  • rand() only gives random number up to RAND_MAX, on CF this is 32767, too small.
  • size() returns an unsigned integer. Doing things such as str.size() - 2 when string size is 1 will overflow. This is especially dangerous when used in a loop.
  • Quicksort.
  • Semicolon instead of comma, and vice versa.
→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

This is a mistake I've seen people make in sieve:

int sieve[n+1];
fill(sieve,sieve+n+1,1);
sieve[0] = 0, sieve[1] = 0;
for(int i=2;i<=n;++i)
    for(int j=i*i;j<=n;++j) //here we have made a mistake already, i*i can overflow, become negative and 
        sieve[j] = 0;       //give segmentation fault on this line.Use ll or start j from 2 instead.

Another mistake that I've made a couple of times is with memset:

int sieve[100000];
memset(sieve,1,sizeof sieve); //mistake made, memset operates byte-wise, you can only set to -1 or 0,

Strictly speaking you can set to other values, but you won't get the expected value. Another mistake which you may make with memset is that you should use sizeof operator only if the bounds are known at compile time.

int* sieve = (int*) malloc(4*n); 
memset(sieve,-1,sizeof sieve); //doesn't work as intended, only first element is -1

Basic thing is that you should be aware it operates byte-wise on underlying memory, not on actual elements.

Other common mistakes include:

1.
int n;
int arr[n];
cin>>n;

2.
int a,b,c;
cin>>a>>b;
c = 1LL*a*b%50; //okay
c = a*1LL*b%50; //okay
c = a*b*1LL%50; //error

3.
//okay this is just carelessness, but it's easy to make
if( (exp)%2==1 )
//is semantically same as 
if( (exp)&1==1 )
//but practically different. % operator and & operator have different precedence, so they give different answers.

4.
//custom comparator for library-based sorting.
//the sorting function asks the question : "is element a before b in the strict-weak-ordering that you define ?"
bool comp(int a,int b)
{
   return (a<=b); //mistake, because if(a==b) then by strict ordering it is not absolutely necessary
//that a come before b, this can get very murky if you are dealing with custom objects.
//best thing to do is to return a 0 if there is no preference, if there are still errors, then you need
//to get into the details of strict-weak-ordering, which can get complicated for custom objects, but is
//essential nevertheless.
}

5.
//pow() function,seriously guys, never use pow for int^int, it's horrible and fails you silently.

int r1 = pow(5,9),r2 = 5;
for(int i=0;i<8;++i)
    r2*=5;
assert(r1==r2); 

//this code fails on my machine, i5, 8gb ram, win10, g++ version gcc 6.3.0
//the answer given by pow is off by 1, the reason is that pow returns double, so you need to use round
//you can easily overlook this and make the mistake I made above in a time-pressure setting
//but in my humble opinion its better to avoid pow altogether for integers, it can have many pitfalls,
//use fast-expo instead.

Finally, I read through all other comments so far, I have made some of the mistakes you all have mentioned and I could easily make the other ones too(Thankfully now I won't :-P). Hope to see more such posts on codeforces :-).

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

    if( (exp)%2==1 ) //is semantically same as if( (exp)&1==0 ) Isn't that: if( (exp)%2==1 ) //is semantically same as if( (exp)&1==1 )

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

If a problem has multiple subtasks where the only difference between them are the constraints, and if you use fixed array sizes...

Forgetting to updated your array sizes before submitting the same solution to the larger subtask.

const int MAXN = 205; // but MAXN = 5005 in larger subtask. :(
int n, a[MAXN];

cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Using a map<double,int> for mapping a number of the form p/q to an integer, instead of using map<pair<int,int>,int> where the key is a pair of numerator and denominator after dividing both (numerator and denominator ) by their gcd. Using double datatype as key may give precision errors.

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

In multiple-testcases format, sometimes there is a tricky case like "if N = 2, then output -1", ignoring the content of the array. So yeah.. next testcases will be hella messed up.

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

Use i += d in Java, where i has type int and d has type double.
Because in other cases you expect compile error when you data can be truncated, but in this case it is not even a warning!

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

Don't know if this is technically a programming bug, but misreading problem statement can be a really horrible way to get WA. With other bugs, at least you can eventually figure it out after a while of debugging. But this one could ruin your entire contest if you don't notice your misconception soon enough.

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

Not accounting for the N = 1 case in tree/array/graph/etc. problems. It was several days into our (sort of CC-Long-styled) olympiad eliminations, and I chuckled when I found that special case...

Also, not knowing the intricacies of your chosen input format. For instance, when to use cin.ignore(); or when to use %c%c in place of %c in scanf, how large to set a char[] for input purposes... that sort of thing.

→ Reply