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:
The output should be $$$10^{18}$$$. But if you run the code, you will get a different output. Why?
Mistake 2
Check out the following code:
Try to run this locally. What is the time complexity of this?
Is it $$$O(n)$$$?
Mistake 3
Check out the following code:
Notice that it is guaranteed that total sum of n is <= 100000
. So how many operations will the code take in the worst case?
Mistake 4
What is happening in the following code?
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?
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.
Mistake 7
Run the following code
You might expect the output to be $$$-1$$$. But the output is actually 18446744073709551615
! Why?
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.
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?
Mistake 10
Look at the following code
The output is not $$$4$$$! Why?
Mistake 11
Is the following code correct?
If it's not, where is the problem?
Mistake 12
Consider the following code for calculating the maximum occurrence in an array.
This code seems like it should work fast enough but in fact, for certain inputs, it will get TLE.
Mistake 13
Let's erase an element from a multiset
.
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$$$.
Mistake 14
Run the following code:
What will be the size of the map? $$$5$$$?
Mistake 15
Let's compute the sum of natural numbers using set!
The time complexity of this solution is clearly $$$O(n \, \log{n})$$$, right?
Mistake 16
Check out the following code:
What is the time complexity of this?
Mistake 17
Let's look at the following simple code.
Can you guess where the bug is?
Mistake 18
Consider the following code to count unique elements in an array.
What's wrong with this code?
Mistake 19
Lots of mistakes can happen while doing modular arithmetic.
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:
It doesn't output $$$3 \cdot 10^{12}$$$.
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:
You can do similar stuff for cbrt()
too.
Mistake 22
Check this out.
What is the time complexity of this solution?
More Mistakes
- Do not
insert
orerase
from a container (set
,vector
etc) while traversing it usingfor (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 valuerand()
generates is32767
? 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 aslong long
, at times, might be 2 times slower thanint
. Uselong 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 gettingRuntime 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 as1
isint
and doing1 << 40
will produce the result inint
, but $$$2^{40}$$$ is way too large to be stored in anint
variable. To fix this issue, use1LL << 40
(basically set the type of1
tolong long
first, check here).- While comparing two floating point numbers, instead of
if (a == b)
, useif (abs(a - b) < eps)
whereeps = 1e-9
or something similar to avoid precision issues. - If you want to take the ceiling of
a / b
wherea
andb
are positive integers, then do(a + b - 1) / b
, instead ofceil(1.0 * a / b)
. For floors just usea / 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 theSolve - 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.