Competitive Programming

Competitive Programming - Some causes of Wrong Answer verdict

14 Aug 2019 ~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;
}