Блог пользователя robot-dreams

Автор robot-dreams, история, 6 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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.
»
6 лет назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +137 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 :)

»
6 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Whiskey

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -21 Проголосовать: не нравится

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

}

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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
    
    
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      there is not too much difference between your and mine implementation

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        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 :)).

»
6 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

not printing the answer ;p

»
6 лет назад, # |
  Проголосовать: нравится +92 Проголосовать: не нравится

Mixing up loop variables. I do this quite often:

for(i=0;i<n;i++)
{
 // lots of code
 for(i=0;i<x;i++);
}
»
6 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

forgetting to comment out the output used for debugging lol

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится -6 Проголосовать: не нравится

    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++.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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)...

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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
»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
  • 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 ;(

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
for(int i=0;i*i<n;i++)
{
    ...
}

In case n is very large

»
6 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится
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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

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.
»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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 :-).

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 )

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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];
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.