robot-dreams's blog

By robot-dreams, history, 8 months 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

»
8 months 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.
»
8 months 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.

»
8 months 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

»
8 months ago, # |
  Vote: I like it +64 Vote: I do not like it

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

»
8 months 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

  • »
    »
    8 months 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 :)

»
8 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Whiskey

»
8 months 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

}

  • »
    »
    8 months 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
    
    
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      there is not too much difference between your and mine implementation

      • »
        »
        »
        »
        8 months 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 :)).

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

not printing the answer ;p

»
8 months 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++);
}
»
8 months ago, # |
  Vote: I like it +22 Vote: I do not like it

forgetting to comment out the output used for debugging lol

  • »
    »
    8 months 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.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++.

  • »
    »
    8 months 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.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can use cerr instead of cout to debug. cerr writes to the standard error stream which is not seen by the online judge.

    Example:

    instead of cout << "x is " << x << '\n';

    you can use cerr << "x is " << x << '\n';

    One drawback of this is that cerr increase the runtime of a program. The runtime of the below program would decrease if the cerr statements were removed.

    vector<int> adj[N];
    
    void dfs(int node, int level) {
    	cerr << node << " " << level << "\n";
    	// do something
    	for (int neighbor : adj[node])
    		dfs(neighbor);
    }
    

    We are facing a trade-off between coding time and running time.

    When our solution seems good, we should remove some debugging statements which consume some time.

»
8 months 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

»
8 months 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++)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    using for (int i = 0; i < s.size(); i++) instead of for (int i = 0; i < (int) s.size(); i++)

»
8 months 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)...

»
8 months 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)

»
8 months 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
»
8 months 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 ;(

»
8 months 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

»
8 months 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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
8 months 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.
»
8 months 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 :-).

  • »
    »
    8 months 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 )

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Multiplying two integers x and y where x,y >= 1e9 without typecasting them to long or doing something like this 1L*x*y.

»
8 months 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];
»
8 months 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.

»
8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Remember to use long long!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

»
8 months 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!

»
8 months 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.

»
8 months 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.