robot-dreams's blog

By robot-dreams, history, 4 weeks ago, ,

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
•

 » 4 weeks ago, # |   +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.
 » 4 weeks ago, # |   +73 Reading n edges instead of n-1 edges when dealing with a tree.
 » 4 weeks ago, # |   +18 Not using int64_t or long long when the some variable can be more than 32 bits
 » 4 weeks ago, # |   +64 Using doubles when it's possible to use long long entirely
 » 4 weeks ago, # |   +137 Though non-preventable, the prime cause of WA is trying to solve problems. :P
•  » » 4 weeks ago, # ^ |   +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 :)
 » 4 weeks ago, # |   +26 Whiskey
 » 4 weeks ago, # | ← 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}
•  » » 4 weeks ago, # ^ |   +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 
•  » » » 4 weeks ago, # ^ |   -8 there is not too much difference between your and mine implementation
•  » » » » 4 weeks ago, # ^ |   +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 :)).
 » 4 weeks ago, # |   -7 not printing the answer ;p
 » 4 weeks ago, # |   +92 Mixing up loop variables. I do this quite often: for(i=0;i
•  » » 4 weeks ago, # ^ |   +6 You can use the -Wshadow flag to help find these.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +14 I think not. He's not re-declaring the variable, but re-using it. Or even something like this: for(int i = 0;i < n;i++){ for(int j = 0;i < n;i++){ // do something } } 
•  » » » » 4 weeks ago, # ^ |   0 Oh true I didn't notice that
•  » » » » 4 weeks ago, # ^ |   0 One of the main reasons I created python style range function for myself
 » 4 weeks ago, # |   +22 forgetting to comment out the output used for debugging lol
•  » » 4 weeks ago, # ^ | ← 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.com/blog/entry/60890Or you can probably just write a lot of garbage, then put it in every solution to get something similar in C++.
•  » » 4 weeks ago, # ^ | ← 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.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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 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.
 » 4 weeks ago, # |   +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
 » 4 weeks ago, # |   +24 Using for (int i = 0; i <= s.size() — 1; i++) instead of for (int i = 0; i < s.size(); i++)
•  » » 4 weeks ago, # ^ |   0 using for (int i = 0; i < s.size(); i++) instead of for (int i = 0; i < (int) s.size(); i++)
 » 4 weeks ago, # |   +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)...
•  » » 4 weeks ago, # ^ |   +5 -Wparentheses (turned on with -Wall too) is your friend: https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html
 » 4 weeks ago, # |   +5 Our team has made a special list of possible reasons of getting wa: link (in russian)
•  » » 4 weeks ago, # ^ |   0 bool f(); returns bool is my favourite one
 » 4 weeks ago, # |   +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#include "bits/stdc++.h" using namespace std; double x=123456789123456789.38438; int main() { cout<
 » 4 weeks ago, # | ← 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 ;(
 » 4 weeks ago, # |   +7 for(int i=0;i*i
 » 4 weeks ago, # |   +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
•  » » 4 weeks ago, # ^ |   +5 And when n is large forgetting to write 1LL*i*i :(
 » 4 weeks ago, # | ← 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.
•  » » 4 weeks ago, # ^ |   +40 Forgetting three corner cases.
 » 4 weeks ago, # | ← 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 :-).
•  » » 4 weeks ago, # ^ |   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 )
•  » » » 4 weeks ago, # ^ |   0 you are right, edited, thanks !
 » 4 weeks ago, # |   -7 Multiplying two integers x and y where x,y >= 1e9 without typecasting them to long or doing something like this 1L*x*y.
 » 4 weeks ago, # |   +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]; 
 » 4 weeks ago, # |   0 Using a map for mapping a number of the form p/q to an integer, instead of using map,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.
 » 4 weeks ago, # | ← 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.
 » 4 weeks ago, # |   0 Remember to use long long!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 » 4 weeks ago, # |   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!
 » 4 weeks ago, # |   +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.
 » 4 weeks ago, # |   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.