One thing is for sure. You do make mistakes. I also make miskates and that's what makes us human. But what we can surely do is — to try to minimize the errors that we make throughout our life.
I have compiled some of the mistakes that I made in my early Competitive Programming phase. I also mentioned how to avoid them. Also, in most cases, I will give you a chance to find out what the bug is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in C++ as it is the most used language for CP.
So, if you are new to CP, stick with me as you might don't wanna repeat the mistakes that I made when I was a beginner.
Mistake 1
Check out the following code:
Code#include<bits/stdc++.h>
using namespace std;
int main() {
int a = 1000'000'000,b = 1000'000'000;
long long product = a * b;
cout << product << '\n';
return 0;
}
The output should be $$$10^{18}$$$. But if you run the code, you will get a different output. Why?
ReasonOverflow!
Even if you declared the product
variable as long long
, what's happening, in reality, is, first the compiler is multiplying a
with b
and then it is assigning the output to the product
variable and as a
and b
both are int
, that's why the output is also int
, but $$$10^{18}$$$ is too much to contain for an int
variable.
So how to solve this?
SolutionTypecast!
#include<bits/stdc++.h>
using namespace std;
int main() {
int a = 1000'000'000,b = 1000'000'000;
long long product = (long long) a * b;
cout << product << '\n';
return 0;
}
Mistake 2
Check out the following code:
Code#include<bits/stdc++.h>
using namespace std;
int get_size(vector<int> a) {
return (int)a.size();
}
int main() {
int n = 1000000;
vector<int> a(n, 0);
long long sum = 0;
for (int i = 1; i <= n; i++) {
sum += get_size(a);
}
cout << sum << '\n';
return 0;
}
Try to run this locally. What is the time complexity of this?
Is it $$$O(n)$$$?
SolutionNope! The complexity is actually $$$O(n^2)$$$.
This is because you are passing the vector by value
— meaning every time you are calling the function the whole vector of $$$10^6$$$ elements is getting passed in the function. So how to solve this?
Refer HerePass by reference
. That is — pass directly the address of the vector.
Code#include<bits/stdc++.h>
using namespace std;
int get_size(vector<int> &a) {
return (int)a.size();
}
int main() {
int n = 1000000;
vector<int> a(n, 0);
long long sum = 0;
for (int i = 1; i <= n; i++) {
sum += get_size(a);
}
cout << sum << '\n';
return 0;
}
Check out this for more.
Mistake 3
Check out the following code:
Code#include<bits/stdc++.h>
using namespace std;
const int N = 100000;
int main() {
int test_cases = 100000;
while (test_cases--) {
int n; cin >> n;
vector<int> a(N, 0);
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
cout << sum << '\n';
}
// it is guaranteed that total sum of n is <= 100000
return 0;
}
Notice that it is guaranteed that total sum of n is <= 100000
. So how many operations will the code take in the worst case?
SolutionIt's not $$$100000$$$. It's actually around $$$10^{10}$$$ as every time you are declaring a vector of size $$$10^5$$$. I used to do this mistake a lot in the beginning. How to solve this?
CodeJust declare a vector only as much as we need.
#include<bits/stdc++.h>
using namespace std;
const int N = 100000;
int main() {
int test_cases = 100000;
while (test_cases--) {
int n; cin >> n;
vector<int> a(n, 0);
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
cout << sum << '\n';
}
// it is guaranteed that total sum of n is <= 100000
return 0;
}
Also, check this out.
Mistake 4
What is happening in the following code?
Code#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 5;
int a[n];
memset(a, 1, sizeof a);
for (int i = 0; i < n; i++) {
cout << a[i] << ' ';
}
cout << '\n';
return 0;
}
The output is supposed to be 1 1 1 1 1
. But it's not the case actually! It's 16843009 16843009 16843009 16843009 16843009
instead. Why?
Reasonmemset
function is actually for char
or 1 byte
data types! Check out this to learn more.
Then you might ask I have seen people doing memset(a, -1, sizeof a)
or memset(a, 0, sizeof a)
. Well, that's because it works for $$$0$$$ and $$$-1$$$ accidentally! Check out this comment to learn why memset
works for $$$0$$$ and $$$-1$$$ correctly.
Using memset
to set all elements in an array to $$$-1$$$ or $$$0$$$ is cool as it works really faster than just looping through all the indices and setting them to $$$-1$$$ or $$$0$$$. But be careful while using it for other numbers.
Mistake 5
Don't use endl
! If your code needs to print millions of newlines, then using endl
turns out to be really slower than using '\n'
. Why?
Mistake 6
Never use pow()
function for integer calculations.
Why?Don't use pow()
unless you are bound to use this because sometimes the answer won't be exactly what you are expecting, and there will be slight precision errors. For example, it's clear that log2(1 << 30)
is $$$30$$$. But sometimes it may consider it as $$$29.9999999999999$$$ and when converting it to int
, it will return 29
.
Similar to this, as pow()
takes double
as arguments, pow(5, 2)
should return $$$5^2=25.00$$$, but sometimes it may consider it as $$$24.9999999999999$$$ and when converting it to int, it will return $$$24$$$. You may use round(pow(5, 2))
in this particular case to avoid the precision issue or just brute force.
Mistake 7
Run the following code
Code#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> v;
cout << v.size() - 1 << '\n';;
return 0;
}
You might expect the output to be $$$-1$$$. But the output is actually 18446744073709551615
! Why?
ReasonCheck this out. Or in short, v.size()
acts more like unsigned
data types.
SolutionJust typecast!
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> v;
cout << (int)v.size() - 1 << '\n';;
return 0;
}
That's why the following code will run indefinitely.
Code#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> v;
for (int i = 0; i < v.size() - 1; i++) { // use i < (int)v.size() - 1 here
// do something
}
return 0;
}
Mistake 8
Using cerr
might be a good way to debug your code as it doesn't output to the standard output. But leaving the cerr
instances in your code while submitting in OJ might be one of the worst ways of getting TLE.
Check this out for more.
Mistake 9
You should always use Fast IO that's for sure. But check out the following code.
Code#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 1; i <= 3; i++) {
cout << i << '\n';
printf("%d\n", i + 10);
}
return 0;
}
You might expect the output to be:
But actually, that might not be the case! For example, locally I am getting the following output:
Basically, the cout
outputs and printf
outputs seem to be working independently! Why?
ReasonThat's because the synchronization has been turned off using the line ios_base::sync_with_stdio(0)
. Check this out to know more.
So do not mix C-style and C++-style printers after using ios_base::sync_with_stdio(0)
.
Mistake 10
Look at the following code
Code#include<bits/stdc++.h>
using namespace std;
int main() {
int a = 1, b = 3;
// we want to take b & 3 and add it to a
int result = a + b & 3;
cout << result << '\n';
return 0;
}
The output is not $$$4$$$! Why?
ReasonThe precedence of the +
operator is higher than the &
operator, so the operator +
operates first, meaning a+b = 4
executes and then the &
operator comes into play, so 4&3
executes and the output is clearly 0
for this.
Check out this to learn more about C++ operator precedence.
So how to solve this issue?
SolutionAlways use brackets for these kinds of situations when you don't know which operator will execute first.
#include<bits/stdc++.h>
using namespace std;
int main() {
int a = 1, b = 3;
// we want to take b & 3 and add it to a
int result = a + (b & 3);
cout << result << '\n';
return 0;
}
Another similar classic error is 1 << n - 1
is not $$$2^{n}-1$$$, it's actually $$$2^{n-1}$$$ as -
has more precedence than the <<
operator.
Mistake 11
Is the following code correct?
Code#include<bits/stdc++.h>
using namespace std;
const int INF = 1e6;
int main() {
int minimum = INF;
for (int i = 1; i <= 10; i++) {
int x; cin >> x; // the value of x can be up to 10000
minimum = min(minimum, x * x);
}
cout << minimum << '\n';
return 0;
}
If it's not, where is the problem?
SolutionBeginners sometimes don't care about the INF
value. For example, here the value of x
can be up to $$$10000$$$, meaning the value of x*x
, will be up to $$$10^8$$$. But here the value of the minimum
variable has been set to $$$10^6$$$, which is not large enough.
So always make sure that the initialized value of a variable is large enough (or small enough).
Mistake 12
Consider the following code for calculating the maximum occurrence in an array.
Code#include<bits/stdc++.h>
using namespace std;
unordered_map<int, int> mp;
int main() {
int n = 300000;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
mp[x]++;
}
int max_occurrence = 0;
for (auto [val, cnt]: mp) {
max_occurrence = max(max_occurrence, cnt);
}
cout << max_occurrence << '\n';
return 0;
}
This code seems like it should work fast enough but in fact, for certain inputs, it will get TLE.
Why?Because of unordered map
! The worst-case time complexity of our code is $$$O(n^2)$$$, that's because unordered map
is a hash map and it might take more than $$$O(1)$$$ operations to insert or access in case of the input is not random.
Check this post: Blowing up unordered_map, and how to stop getting hacked on it
So always use a custom hash if you don't want to get blown up.
Mistake 13
Let's erase an element from a multiset
.
Code#include<bits/stdc++.h>
using namespace std;
int main() {
multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
// now erase one occurrence of 2
se.erase(2);
// now print the elements
for (auto val: se) {
cout << val << ' ';
}
cout << '\n';
return 0;
}
The output is not 1 1 2 2 3 4 5 5
. It's actually 1 1 3 4 5 5
! Seems like we have erased all occurrences of $$$2$$$.
Why?That's because if you use a value in the erase()
function in a multiset
, then all elements will be erased, but if you erase an iterator
, then only the element in that iterator will get erased. Check this out for more.
Solution#include<bits/stdc++.h>
using namespace std;
int main() {
multiset<int> se({1, 1, 2, 2, 2, 3, 4, 5, 5});
// now erase one occurrence of 2
se.erase(se.find(2));
// now print the elements
for (auto val: se) {
cout << val << ' ';
}
cout << '\n';
// 1 1 2 2 3 4 5 5
return 0;
}
Mistake 14
Run the following code:
Code#include<bits/stdc++.h>
using namespace std;
int main() {
map<int, int> mp;
// add 1 to 5 to the map
for (int i = 1; i <= 5; i++) {
mp[i]++;
}
int cnt = 0;
// check how many numbers from 1 to 10 exist in the map
for (int i = 1; i <= 10; i++) {
if (mp[i]) {
++cnt;
}
}
// now print the size of the map
cout << (int)mp.size() << '\n';
return 0;
}
What will be the size of the map? $$$5$$$?
CheckNo! It's actually $$$10$$$.
That's because of the statement if (mp[i])
, mp[i]
also inserts the element i
into the map even if it doesn't exist. This type of error might get you some unexpected MLEs.
But how to solve this?
Solution#include<bits/stdc++.h>
using namespace std;
int main() {
map<int, int> mp;
// add 1 to 5 to the map
for (int i = 1; i <= 5; i++) {
mp[i]++;
}
int cnt = 0;
// check how many numbers from 1 to 10 exist in the map
for (int i = 1; i <= 10; i++) {
if (mp.find(i) != mp.end()) {
++cnt;
}
}
// now print the size of the map
cout << (int)mp.size() << '\n';
return 0;
}
Mistake 15
Let's compute the sum of natural numbers using set!
Code#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 100000;
set<int> se;
for (int i = 1; i <= n; i++) {
se.insert(i);
}
// compute the sum of 1 to n
long long sum = 0;
for (int i = 1; i <= n; i++) {
// get the iterator containing the smallest element >= i
// it will point to i here
auto it = lower_bound(se.begin(), se.end(), i);
sum += *it; // *it = i
}
cout << sum << '\n';
return 0;
}
The time complexity of this solution is clearly $$$O(n \, \log{n})$$$, right?
Right?Wrong!
It's actually $$$O(n^2)$$$. Wait, but doesn't lower_bound
work in $$$O(\log{n})$$$?
Actually lower_bound(set.begin(), set.end(), value)
is not $$$O(\log{n})$$$! Check out this to learn more.
Then What to Do?Use set.lower_bound(value)
, it's $$$O(\log{n})$$$.
#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 100000;
set<int> se;
for (int i = 1; i <= n; i++) {
se.insert(i);
}
// compute the sum of 1 to n
long long sum = 0;
for (int i = 1; i <= n; i++) {
// get the iterator containing the smallest element >= i
// it will point to i here
auto it = se.lower_bound(i);
sum += *it; // *it = i
}
cout << sum << '\n';
return 0;
}
Same for upper_bound
.
Mistake 16
Check out the following code:
Code#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 1000000;
string s = "";
for (int i = 0; i < n; i++) {
s = s + 'a'; // append a to the string
}
cout << s << '\n';
return 0;
}
What is the time complexity of this?
SolutionIt's not $$$O(n)$$$! It's $$$O(n^2)$$$ actually.
Because every time you are using s = s + 'a'
, on the right side it is accessing the whole string s
(which can be $$$O(n)$$$ in size). How to fix this?
CheckUse s += 'a'
syntax, as now we are not accessing the whole string every time.
Code#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 1000000;
string s = "";
for (int i = 0; i < n; i++) {
s += 'a'; // append a to the string
}
cout << s << '\n';
return 0;
}
Mistake 17
Let's look at the following simple code.
Code#include<bits/stdc++.h>
using namespace std;
int main() {
int test_cases; cin >> test_cases;
// take an array of length n as input
// print YES if the length is 1 or NO otherwise!
while (test_cases--) {
int n; cin >> n; // length of the array
if (n == 1) {
cout << "YES\n";
continue;
}
vector<int> a(n);
for (int i = 0; i < n; i++) { // taking the array elements as input
cin >> a[i];
}
cout << "NO\n";
}
return 0;
}
Can you guess where the bug is?
BugWhen n == 1
, you are continuing even before taking the array as input. So the code will give WA in some cases.
It happened to me multiple times before! So please take the whole input first if you want to continue by checking some base cases.
Solution#include<bits/stdc++.h>
using namespace std;
int main() {
int test_cases; cin >> test_cases;
// take an array of length n as input
// print YES if the length is 1 or NO otherwise!
while (test_cases--) {
int n; cin >> n; // length of the array
vector<int> a(n);
for (int i = 0; i < n; i++) { // taking the array elements as input
cin >> a[i];
}
if (n == 1) {
cout << "YES\n";
continue;
}
cout << "NO\n";
}
return 0;
}
Mistake 18
Consider the following code to count unique elements in an array.
Code#include<bits/stdc++.h>
using namespace std;
const int MAX_ELEMENT = 1e5;
int cnt[MAX_ELEMENT + 1];
int main() {
int test_cases; cin >> test_cases;
while (test_cases--) {
int n; cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
cnt[x]++;
}
int unique_elements = 0;
for (int i = 0; i <= MAX_ELEMENT; i++) {
if (cnt[i] > 0) {
unique_elements++;
}
}
cout << unique_elements << '\n';
}
return 0;
}
What's wrong with this code?
BugNotice that the problem has multiple test cases. But you are not resetting the cnt
array in each test! So the counts of previous test cases will still be in the cnt
array and will produce WA.
So always clear everything from the previous tests.
Code#include<bits/stdc++.h>
using namespace std;
const int MAX_ELEMENT = 1e5;
int cnt[MAX_ELEMENT + 1];
int main() {
int test_cases; cin >> test_cases;
while (test_cases--) {
int n; cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
cnt[x]++;
}
int unique_elements = 0;
for (int i = 0; i <= MAX_ELEMENT; i++) {
if (cnt[i] > 0) {
unique_elements++;
}
}
cout << unique_elements << '\n';
// resetting everything
for (int i = 0; i <= MAX_ELEMENT; i++) {
cnt[i] = 0;
}
}
return 0;
}
Mistake 19
Lots of mistakes can happen while doing modular arithmetic.
Example Mistakes#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main() {
int a = 1e9, b = 1e9, c = 1e9;
int sum = (a + b + c) % mod;
cout << sum << '\n';
int product = a * b % mod;
cout << product << '\n';
int random = 1LL * a * (b * c % mod) % mod;
cout << random << '\n';
a = 1e8;
int sub = (a - b) % mod;
cout << sub << '\n';
return 0;
}
Where are the Bugs?#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main() {
// 0 <= a, b, c < mod
int a = 1e9, b = 1e9, c = 1e9;
int sum = (a + b + c) % mod;
// overflow as (a + b + c) > INT_MAX(=2147483647)
// better way: ((a + b) % mod + c) % mod
cout << sum << '\n';
int product = a * b % mod;
// overflow as a * b > INT_MAX
// better way: 1LL * a * b % mod
cout << product << '\n';
int random = 1LL * a * (b * c % mod) % mod;
// overflow in the (b * c % mod) part
// correct way: 1LL * a * (1LL * b * c % mod) % mod
// better way: 1LL * a * b % mod * c % mod
cout << random << '\n';
a = 1e8;
int sub = (a - b) % mod;
// not overflow, but when a < b, it will produce a negative number
// better way: (a - b + mod) % mod
cout << sub << '\n';
// Also always make sure that after each arithmetic operation
// All of your variables are in the range [0, mod-1]
return 0;
}
So while doing modular arithmetic, always make sure that after each operation, all your variables are $$$\ge 0 $$$ and $$$< MOD$$$, and you haven't done any overflow.
Mistake 20
Look at the following code:
Code#include<bits/stdc++.h>
using namespace std;
int main() {
long long val= 1e12;
vector<long long> v({val, val, val});
// now take sum of all elements
long long sum = accumulate(v.begin(), v.end(), 0);
cout << sum << '\n';
return 0;
}
It doesn't output $$$3 \cdot 10^{12}$$$.
Why?That's because the initialized variable (0
) is an int
, so the sum also returns as int
. Check this out for more.
SolutionCode#include<bits/stdc++.h>
using namespace std;
int main() {
long long val= 1e12;
vector<long long> v({val, val, val});
// now take sum of all elements
long long sum = accumulate(v.begin(), v.end(), 0LL); // typecast
cout << sum << '\n';
return 0;
}
So always make sure that the init variable is correct or not.
Similar Mistake#include<bits/stdc++.h>
using namespace std;
int main() {
vector<double> v({1.23, 2.05, 3.003});
// now take sum of all elements
double sum = accumulate(v.begin(), v.end(), 0); // correct way: 0.0
cout << sum << '\n'; // it outputs 6 which is not intended
return 0;
}
Mistake 21
Using sqrt()
for integers directly might cause some precision issues and give you wrong results.
One of the best ways to compute square roots is the following:
Solutionlong long x = (long long)1e18 - 1;
long long k = sqrtl(x);
while (k * k < x) ++k;
while (k * k > x) --k;
cout << k << '\n';
You can do similar stuff for cbrt()
too.
Mistake 22
Check this out.
Code#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 100000;
multiset<int> se;
// insert n instances of 1
for (int i = 1; i <= n; i++) {
se.insert(1);
}
long long tot = 0;
// let's count how many 1s are there in the multiset, n times
for (int i = 1; i <= n; i++) {
tot += se.count(1);
}
cout << tot << '\n';
return 0;
}
What is the time complexity of this solution?
CheckIt's not $$$O(n \, \log{n})$$$, it's actually $$$O(n^2)$$$!
Why? Because the time complexity is logarithmic in the size of the container + linear in the number of occurrences of the element and here, the occurrence of $$$1$$$ is $$$n$$$. So use the count()
function for multisets carefully!
Also, if you want to check if a number exists in a multiset use the find()
function instead of counting the occurrences.
More Mistakes
- Do not
insert
or erase
from a container (set
, vector
etc) while traversing it using for (auto val: container)
like syntax at the same time. Because for dynamic containers inserting or erasing from it might change the structure of the container. So traversing it parallelly might cause some unexpected behavior. - Use
setprecision
for printing floating point numbers, otherwise, you might get WA for precision issues. - Do not use
rand()
function to generate random numbers. Also, did you know that the maximum value rand()
generates is 32767
? Check out Don't use rand(): a guide to random number generators in C++ to learn what to use. - Create variables only when you need them instead of just declaring
int a, b, c, d, e, f, g, h;
and 69 other variables at the beginning of your code! This will help you catch unnecessary bugs when you use the same variable in two or more places. - Do not use
long long
everywhere as long long
, at times, might be 2 times slower than int
. Use long long
only when it's necessary. - If you want to count the number of set bits in a
long long
number, then use the __builtin_popcountll
function instead of the __builtin_popcount
function. - In C++, the comparator should return false if its arguments are equal. You might get
Runtime Error
if you don't do this. - Speaking of
Runtime Error
, the most likely case of getting Runtime Error
is not declaring the array sizes with enough large values. Check out the constraint of the problem to make sure of it. long long x = 1 << 40
will still overflow as 1
is int
and doing 1 << 40
will produce the result in int
, but $$$2^{40}$$$ is way too large to be stored in an int
variable. To fix this issue, use 1LL << 40
(basically set the type of 1
to long long
first, check here). - While comparing two floating point numbers, instead of
if (a == b)
, use if (abs(a - b) < eps)
where eps = 1e-9
or something similar to avoid precision issues. - If you want to take the ceiling of
a / b
where a
and b
are positive integers, then do (a + b - 1) / b
, instead of ceil(1.0 * a / b)
. For floors just use a / b
as it will round down to the nearest integer. - If you want to take the floor of the log of an integer $$$n > 0$$$ (same as finding the highest set bit of $$$n$$$), use
__lg(n)
. Clean, fast, and simple. - Slightly Advanced: While string hashing, do not use $$$2^{64}$$$ as your mod, and always use at least 2 different primes and mods. Check out Anti-hash test.
Non-technical mistakes
- Instead of the
Solve - Code
structure, use the Solve - Design - Code
approach. Try to design what you will code before jumping to the coding part right away. This will significantly lessen your wrong submission counts and will save lots of time. - You might use
#define int long long
and make your code pass, but you should understand why your solution was not passing in the first place. What I am trying to say is — Learn to control your code. - Solve problems out of your comfort zone and do not just stick to easier problems. Learning new things by solving problems is more important than just increasing your solve count without learning anything new. "Stop obsessing over the number of hours spent or problems solved. These numbers don't mean shit because the variance is so high and it is very easy to spend a lot of time and solve a lot of problems without learning anything." — Tähvend Uustalu (-is-this-fft-).
- Do not skip on the Time and Space Complexity of your solution just because you got AC in the problem. This is really important for a beginner that will help you in the long run.
- Specially on Codeforces, you might get AC by just guessing the solution. But you should learn to prove the solution if you want your brain to get anything out of the problem.
- Not reading others' code is a great way to miss out on learning new techniques/ways to solve the same problem. You should always read the solutions of some of the best coders to know the different ways of solving a problem.
- Do not bother about rating before learning the basics of CP.
- Use a better coding style as it will be helpful in team contests and while debugging your solution. One example coding style is this.
- One way to improve your coding practice is to break your solution down into smaller, more manageable pieces. Instead of attempting to write the entire solution at once, focus on writing and debugging one part at a time. This approach can make it easier to identify and fix errors, and can also make the coding process much easier.
- Maybe you are not as good as you are thinking right now! Maybe your current practice method is not as good as you are assuming! Check out Self-deception: maybe why you're still grey after practicing every day for more.
- Mistake on facing failures: "For me, failing in contests shows me that I still have much to learn so I try to learn new stuff and that's most of the fun. The rest is seeing practice paying off every once in a while. If everyone could have good performances all the time, nobody would have to practice to get better right?" — Tiago Goncalves(tfg). I agree with Tiago. I think the most fun part is to try to be better. It's not fun being good all the time and also it's not fun being bad all the time. The fun part is the transition from doing bad to doing good, the actual delta. And if you practice efficiently then you will certainly make progress.
- Surround yourself with like-minded people as this way you will be able to learn a lot more than trying to learn everything alone.
- Not being self-confident: Self-confidence is the key! If you think you can't do it, then you are already lost! "If you think you are beaten, you are, If you think you dare not, you don’t If you like to win, but you think you can’t, It is almost certain you won’t. If you think you’ll lose, you’re lost. For out in the world we find, Success begins with a fellow’s will— It’s all in the state of mind. If you think you are outclassed, you are, You’ve got to think high to rise, You’ve got to be sure of yourself before You can ever win a prize. Life’s battles don’t always go To the stronger or faster man, But soon or late the man who wins Is the man WHO THINKS HE CAN!” — Napoleon Hill, Think and Grow Rich.
- Do not skip over anything from the solving part of the problem including understanding the solution, proving the solution, coding the solution efficiently, and time and space complexity of the solution, especially if you are a beginner. Every time you skip over any necessary parts of the solution incurs a debt to the CP god. Sooner or later, that debt is paid.
- Remember that Getting AC is not the main goal, learning something new by solving the problem is the main goal.
Thanks for reading the blog. Feel free to add more mistakes that are common in CP in the comment section.
See you on a later episode, friend !
In Mistake 4, you are saying "the output is not 1 1 3 4 5 5". However this is the output of the code. I think you wanted to say "the output is not 1 1 2 2 3 4 5 5"
Thanks, fixed!
Me finding upvote button
Thanks
I wonder whether you type "mistakes" as "miskates" in the first paragraph on purpose
I agree with you. One mistake you didn't mention is getting stuck on a single problem during contest and not attempting the next one. D sometimes can be easier than C (look at official submissions in div2). Or the next problem may be easier just for you as it happened to me during Edu 141. So I suggest participating from m1.codeforces.com and never look at solve count.
Also, the maximum value
rand()
returns isRAND_MAX
which is implementation dependent, as stated in the blog you linked.The only thing I disagree with is that using long long everywhere can be harmful. It almost never is. One time I came close to getting TLE (but got accepted anyway) because of this, was when there were many divisions with long long. Compare using long long vs not using it. However, you can get MLE using long long when using 2D or 3D arrays/vectors. One 5000*5000 matrix of long long integers consumes around 190MB which is fine, because ML is usually 256MB. But declaring another one will exceed it. It might happen in DP problems.
One of the mistakes I still make is: returning to early.
For example in the past contest there's a "YES" "NO" question, I returned when getting input.
This is silly and time wasting.
Very helpful tutorial, thank you! Will definitely forward this to my students who are starting competitive programming.
But how did the advice about string hashing end up in a post "Common mistakes I made when I was a beginner"?
Thanks for pointing it out! Added a
slightly advanced
flag.Thanks for this blog .
Wrong Answer ??
Did you read the question properly ? missed something ?
Int overflow
Edge case, n=1? n=0?
Took Input or forgot?
Uninitialised value?
Automatic integer rounding
= or ==Note: The only difference between this problem and problem B1 is that here, scenes are larger and may contain rocks.
MOD during calculation
MOD with subtraction and division ?
MOD with subtraction ex : (11 + (-7)) mod 5
Base Cases ?
0-indexing or 1-indexing
wrong file subitted
Ascending or Descending sort.
Commented Debug statements
forgot printing endl ?
loop i++ or i--
loop mistakes > or >=, j=i or j=1, m/n misplacing, forgot incrementing
output precision for floating point answers
string : s += 'a' + 'c'
sqrt and sqrll, sqrt error ?
abs, absll
cmp should return false if args are equal.
logical Error ? sure logic isn't faulty?
Long long overflow
DP — Proper base cases ?
Using arrays and getting WA instead of Runtime error on out of bound access.
Try coding in python
IO anamoly in using cout and printf together ex : https://www.codechef.com/viewsolution/84270051
Graph : will your soln break for
self loops, multiple edges between a,n, negative weigted cycle/edges
is graph directed?
TLE
fastio ? endl ??
freopen(input.txt) ? forgot to remove ?
Interactive : dont use fastio, use endl or fflush, properly follow IO format
use Global arrays, taking mod less times, use compile time constant for mod
dont ignore value of t, number of testcases.
try in C
is your complexity is O(n) per test case, or O(maxn)
Crazy runtime errors ?
Name collisions, using some reserved names
Some index being used having invalid values, -1, garbage, etc.
Thanks for sharing! Added some of them to the blog.
thanks for sharing! in TLE: 4'th line, what is "taking mod less times, use compile time constant for mod"
In Mistake 10 — Reason, you said that
+
and&
have same precedence. In fact, they have different order of precedence, with+
having much higher priority than&
Thanks a lot. Fixed.
Using
1 << x
instead of1ll << x
has cost me a problem in a contestsame.
In one of the recent contests, I realized that for a set or an STL container not having random access iterators, upper_bound(s.begin(),s.end(),value) has time complexity of O(N) whereas using s.upper_bound(value) has time complexity of O(log n). Check my submissions 188120001 and 188135247.
This is because in upper_bound(s.begin(),s.end(), value), On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average. (Refer here)
In mistake 2, better to pass by const reference--const reference will make the compiler complain if you edit the values at all, which will catch a few bugs.
for mistake 7 we can simply use vector v; cout<<int(v.size())-1<<'\n';
.
Another common mistake is when you return early on a test-case (e.g., due to identifying a special case that's easily handled without much work) before you read all inputs for the test-case, or before you clear out your containers (vectors/maps/etc), which messes with the later test-cases.
One way to avoid these is to get into the habit of reading all inputs before any processing (even if there is a special case that can be easily detected while reading the inputs) and also to clear containers at the start of each test-case (even before reading input) as opposed to the end of each test-case. Having a separate solve function also deals with the latter.
Relatable. I did this too multiple times. Added it to the blog. Thanks.
I suffered a lot from Mistake 9 one year ago. I was doing a team contest and got WA, then spent a whole week trying to understand what's going on until Naseem17 explained it to me. Many mistakes from this list can't be realised without the help of more experienced coder.
I made the same mistake as Mistake-1 few days ago when i was learning C. That time I solved it with another approach but today I learn another approach.
Waiting for the next episode
nice, thanks! I make this blog bookmark!
I also write the blow code at top of my template(I write it in a way that I understand :/)
Great blog!
Forgetting to reset a global array in multitest is also a classic error.
Thanks, added!
You're welcome :)
Accessing a map index can result in insertion. Thus accessing map index too much can result in MLE and TLE.
int a=mp[2]; here 2 gets inserted in mp if it is not already there.
how can I be better at proofing greedy?
I want to add on Mistake 10.
A common mistake I found myself doing is using a bitwise operator, say or and
==
in a single expression without realizing==
has higher precedence than the bitwise operators.Consider the expression
5^5 == 0
.You might expect it to evaluate as
0 == 0
and hencetrue
but it is evaluated as5 ^ (5 == 0)
to5 ^ 0
to5
.yea this is the same as when he did a + b&c. Ppl usually expect it to output (a+(b&c)) whereas it actually outputs ((a+b)&c)
This is quite useful for me. I often make the mistake 10 such as expressing $$$2^n-1$$$ as
1<<n-1
and sometimes stuck in it for a long time. These mistakes is really hard to fix.Assuming $$$g(x)$$$ is a function that got recalculated each time when called wrong.
Which type of code do you do then ?
or
or
Which type of code do you use on real numbers ?
or
or
Which of the following formula do you use:
or
Using
sqrt()
without declaring<cmath>
In Mistake 14 you can use
!mp.count(i)
instead ofmp.found(i) != mp.end()
if you want a shorter version of it. Although I thinkmp.count(i)
is slower thanmp.found(i)
that is becausefound(i)
stops at the first occurrence ofi
unlikecount(i)
which has to travel the whole map.most mistakes are related to c++ only
In mistake 2, why did you typecast a.size() into int??? I know that size() function returns an integer value.
size() return unsigned integer , when vector is empty() , if you write (v.size()-1) then there is no negative number in unsigned integer, it will become INT_MAX, it will run for infinity
Thanks!
Mistake n+1, view the scoreboard in contest time
For python, 3.8 does not have math.lcm but my machine has it. It caused me some damage today. Link
very much helpful for me
great vai
Must needed for cpers. Thanks for this!
This is made of love, thanks a lot man! Appreciate that a lot!
Awesome Blog!
your code for mistake 18 contains mistake 3
about mistake 20, I had a similar mistake once, the following will overflow:
If you really want to use the STL, this works:
Just revisited this amazing blog, no doubt one of the absolute best!