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
- 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
Using
1 << k
instead of1LL << k
when the result won't fit in 32 bitsOnly 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)
- Since C++ priority queues give you the max element by default, you need to initialize with
Using the wrong parameter (e.g.
n
instead ofm
) 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?
I often get WAs on problems with multiple test cases because of
cout << endl;
after end of output for a test case.Reading n edges instead of n-1 edges when dealing with a tree.
Not using int64_t or long long when the some variable can be more than 32 bits
Using doubles when it's possible to use long long entirely
Though non-preventable, the prime cause of WA is trying to solve problems. :P
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 :)
Whiskey
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
}
Why not write it on the top for maintaining convenience? Moreover, I think this kind of implementation is easier:
there is not too much difference between your and mine implementation
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 :)).
not printing the answer ;p
Mixing up loop variables. I do this quite often:
You can use the -Wshadow flag to help find these.
I think not. He's not re-declaring the variable, but re-using it.
Or even something like this:
Oh true I didn't notice that
One of the main reasons I created python style range function for myself
forgetting to comment out the output used for debugging lol
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://mirror.codeforces.com/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++.
I'm a g++ user and usually use as follows:
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.
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
Using for (int i = 0; i <= s.size() — 1; i++) instead of for (int i = 0; i < s.size(); i++)
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
) equalsc
)...-Wparentheses (turned on with -Wall too) is your friend: https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html
Our team has made a special list of possible reasons of getting wa: link (in russian)
bool f(); returns bool
is my favourite oneI 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.
1.23456789123e+17
Use
cout<<fixed<<setprecision(12);
. By doing this, you get precision upto 12 digits after decimal.Forgot to write a piece of code that handles special cases.
Used
n
instead ofm
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 ;(
In case n is very large
instead of
when dealing with divisors and primes and factorization
And when n is large forgetting to write 1LL*i*i :(
Actually I can list a lot more
rand()
only gives random number up toRAND_MAX
, on CF this is 32767, too small.size()
returns an unsigned integer. Doing things such asstr.size() - 2
when string size is 1 will overflow. This is especially dangerous when used in a loop.This is a mistake I've seen people make in sieve:
Another mistake that I've made a couple of times is with memset:
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.
Basic thing is that you should be aware it operates byte-wise on underlying memory, not on actual elements.
Other common mistakes include:
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 :-).
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 )
you are right, edited, thanks !
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.
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.
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.
Use
i += d
in Java, wherei
has type int andd
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!
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.
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
inscanf
, how large to set achar[]
for input purposes... that sort of thing.