Competitive Programming - Some causes of Wrong Answer verdict
~6 min read
In many cases, even though I am certain that I have understood the problem and taken the proper method to solving it, I still receive the dreaded WA verdict. In situations like this, I tend to overlook something from the list below:
- Data type
- Operator precedence
- Modulo operation
- Loop control variable
- Variable initialization
- Clearing data structures
- Corner case
And, there could be some other reasons as well.
I am going to discuss the first 3 points from my checklist a bit more.
1. Data type
A very common mistake of mine involving data types is that it may be the case that the answer is a 32-bit signed positive integer number but an intermediate result is a 64-bit signed positive integer number and since I use 32-bit signed positive integer numbers throughout my code, I get a WA verdict.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 100000;
int m = 1000000;
/*
* (10^5 * 10^6) / 10^4
* (10^11) -> outside of the range
*
* A possible approach to resolve this, given either of n or m is even,
* (10^5 / 10^4) * 10^6 = 10 * 10^6 = 10^7
*/
// wrong approach
int ans = (n * m) / 10000;
printf("%d\n", ans); // 121575
// correct approach
ans = n / 10000 * m;
printf("%d\n", ans); // 10000000
return 0;
}
2. Operator precedence
Look at the C++ operator precedence chart for more details.
I mostly make operator precedence errors while coding up a solution involving bitwise operation. Below is an example of one such error:
#include <bits/stdc++.h>
using namespace std;
int main() {
int mask = 5; // binary -> 0101
int pos = 1;
/*
* 1 << 0 means 2^0
* 1 << 1 means 2^1
* .....
* 1 << n means 2^n
*/
/*
* != has higher precedence than &
* 5 & (1 << 1) != 0
* 5 & 2 != 0
* 5 & true
* true & true
* true
*
* However, the answer expected is false
* and the correct expression,
* resolving precedence error is
* (5 & (1 << 1)) != 0
*/
// wrong approach
if (mask & (1 << pos) != 0) {
printf("No zero value.\n");
} else {
printf("Zero value.\n");
}
// Output: No zero value.
// correct approach
if ((mask & (1 << pos)) != 0) {
printf("No zero value.\n");
} else {
printf("Zero value.\n");
}
// Output: Zero value.
return 0;
}
3. Modulo operation
I face modulo operation issue when my code involves subtraction. I basically miss out on the fact that the big number (after modulo operation) can get smaller than the small number (after modulo operation). Now, subtracting the small number from the big number causes the answer to turn out negative. But, the answer expected is positive.
#include <bits/stdc++.h>
using namespace std;
int main() {
int big_number = 100;
int small_number = 4;
int mod = 7;
/*
* ((100 % 7) - (4 % 7)) % 7
* (2 - 4) % 7
* -2 % 7
* -2
*
* Usually, the answer expected is a positive number
* One approach to resolve this is
* (ans + mod) % mod = (-2 + 7) % 7 = 5
*
*/
// wrong approach
int ans = ((big_number % mod) - (small_number % mod)) % mod;
printf("%d\n", ans); // -2
// correct approach
ans = ((big_number % mod) - (small_number % mod)) % mod;
ans = (ans + mod) % mod;
printf("%d\n", ans); // 5
return 0;
}
Featured Articles
Salary ranges offered by Bangladeshi Software Companies for different positions
The data has been collected via this form.
Recruitment Stories - Proteeti's Experience at Brain Station 23
Proteeti Prova Rawshan is currently working as an Associate Software Engineer at Brain Station 23....