Competitive Programming (CP)
I do Competitive Programming to become a better Problem Solver. Plus, it’s actually very fun to see my rating progress over time.
See Leetcode for more general topics. Doing Competitive programming in C++.
Platforms:
 Codeforces (Goal: Master $→$ 2000)
 DMOJ → Codeforces conversion (x100 + 500)
 LeetCode (weekly contests. Goal: Top 1%)
Sources of Knowledge
 Competitive Programmer’s Handbook
 cpalgorithms.com
 USACO Guide (though I personally haven’t used that much)
 YouTubers: Colin Galen, Errichto, Algorithms Live
 Mathematics for Computer Science by MIT → helpful
 ”How to practice Competitive Programming” by Codeforces
https://github.com/TheCODEPlusPlusCommunity/CompetitiveProgrammingandDSA/blob/main/ROADMAP.md
When you lose motivation for CP, just think about the ego boost when you get that higher rating. It’s addicting. 2000. Orange color. That’s so hot.
I am washed (20230131)
Taking a gap from competitive programming for 4 months has made me really rusty. Solving these easy problems are hard for me. I can’t even do LeetCode medium or easy, THIS IS EMBARRASSING.
Why is this happening? I thought. I guess it’s because your brain is like a muscle. Don’t exercise.
(20230307) Okay, I am slowly getting back into the groove of problemsolving. As I read more and more problems, I get better at reading the problem and understanding it instantly. When I was rusty, I kept misunderstanding the problem, because I haven’t seen those problems in a very long time (hence lost my Pattern Recognition). Also, I get quicker at thinking about the edge cases, it makes me way more sharper.
Well I still kind of struggle with this problem where I really don’t think the problem through, and end up with the wrong solution. When I do more and more practice, this happens a lot less because I get more and more Intuition.
Talking with William about CP
William is an extremely good competitive programmer. He went to CCO and did ICPC in 1st year university. When talking about the value of CP, he says that “doing CP is probably the best use of your time in high school”.
During the time I grinded CP, I felt that I become a whole lot faster at solving problems, even for things outside of CP. I think CP is singlehandedly the best exercise for your brain to do problemsolving skills.
CP generalizes really well (William aslo said this), it makes you come up with solutions so much faster, because you are conditioned to think fast when you do CP, not take your time like a lazy bastard… So CP programmers are much more productive.
20240125: Still Washed
I literally couldn’t come up with the solution for the Diameter of Tree, a LeetCode easy…??? That is embarassing
From SecondThread: “You need to make this really interesting observation”
 And yes, this reminds me that CP forces you to make observations really fast.
I guess competitive programming is really just glorified Pattern Recognition. You look at the problem and see some underlying idea. I get worse because I forget these underlying ideas that you can use to solve these problems.
Traits of great competitive programmers
They come up with really simple and short solutions. Noobs usually come up with overly complex solutions.
Exciting Topics to Master
 Sparse Table
 Lowest Common Ancestor (LCA)
 Fenwick Tree
 Segment Tree
 Sparse Table
 String Algorithms
 Graph Theory → Understand its relationship to DP as well
Other topics that I still don’t understand, but briefly looked at:
 Various DP optimizations
 Bipartite Graph
 Square Root Decomposition
 Fast Fourier Transform
 Treap
 Geometry
My Weaknesses / Painpoints
 Palindrome Problems, solve lots of these!!
 Parsing strings
 Regex
 String Algorithms
 Permutation / subset problems (I REALLY suck at those, I get really intimidated just looking at them)
 Dynamic Programming problems
 Implementation problems
 Always using a Map + C++ Vector as a crutch when really I should have though of Priority Queue
 Debugging stupid errors
 Discovering the greedy algorithm quickly
 Graph Theory problems

 A lot of graph problems don’t actually require you to implement searching. You just need basic Dynamic Programming

What I am getting confident at:
 Graph Theory? NO
Note
A lot of times, I jump straight into the implementation just by intuition without really thinking about the problem.
Thus, I often come up with an initially wrong implementation, such as for this seemingly simple problem: https://codeforces.com/contest/1700/problem/B
Some Challenges
 Whenever I try to solve a problem, and I think about the problem for a bit, then I start getting tired a little bit and want to go to sleep, so that is a pretty annoying issue.
 I underestimate the difficulty of implementing a solution to the problem. I oftentimes come up with a solution that is too simple, and I fail to recognize that the algorithm I design doesn’t work in certain cases, which leads to terrible performance.
Tip
With harder problems, try large test cases and see if your program is fast enough. Avoids wasting a point because you TLE.
Some Key Lessons
Proofs in Competitive Programming are especially important to ensure the correctness of a program. Oftentimes, I am only thinking of a solution by my feeling, without being able to concretely prove it.
 Realize that sometimes, brute force is enough. Do not overthink the problem, such as this one: https://codeforces.com/contest/1686/problem/A
 Speed is super important
 What I have realized from doing CP is that I need to understand the problem faster. Oftentimes, I misunderstand the problem and waste a lot of time implementing something that doesn’t work.
 Learn to read the problem
 The faster you learn, the better you will perform.
SUPER INTERESTING:
 For this problem https://codeforces.com/contest/1682/problem/C, my
unordered_set
implementation is too slow, but theset
version is good I thought that sets are slower than unordered_sets which offer $O(1)$ lookups. However, I think it is probably because there are a lot of collisions which lots of data, so my lookup actually became $O(n)$, when a usual set is at worse $O(gn)$. Super cool!
Common Mistakes
 Forgetting to pass strings by reference, which makes the solution so much slower
 TLE on submissions when I could have easily double checked
 I make tiny mistakes on edge cases that I fail to consider… I think for these things, the only way I can improve is by practicing more and more
 Using the wrong units. I need to understand the Data Types to use, whether for example it is just
int
orlong int
. I tried to store an integer value outside the range of the type.  https://whimsical.com/codeforcescandidatemasterroadmapbylovebabbarCiXPPD3CnwoXPr2d8Ajx1h
Topics
 Data Structure
 Dynamic Programming
 Binary Search
 Graph Theory
 Tree Traversal
 Merge Intervals
 Flows and Cuts
math
Exercises from APS
Implementation Problems (translating solution into code, this is often harder than it seems)
 Flexible Spaces – flexiblespaces
 Sort of Sorting – sortofsorting
 Permutation Encryption – permutationencryption
 Jury Jeopardy – juryjeopardy
 Fun House – funhouse
 Settlers of Catan – settlers2
 Cross – cross
 Basic Interpreter – basicinterpreter
 Cat Coat Colors – catcoat
Thoughts on CP
From Errichto https://www.youtube.com/watch?v=F4rykKLcduI Competitive programmers are really good at thinking of ideas really fast, but are they necessarily good software engineers? No. They always assume that the data is clean, but not always.
Overskilled in certain things that are not important on the job. Platforms
 Codeforces
 TopCoder (old platform)
Math competitions and programming competitions are similar (in terms of the logic)
Sometimes, in competitive programming, you don’t implement the solution with the lowest runtime complexity. For example, something with $O(ngn)$ runtime in theory can be faster IRL than something with $O(n)$.
Algorithms live
https://www.youtube.com/watch?v=Oq1seKJvfQU&ab_channel=AlgorithmsLive%21
 The idea of probing: Look at the optimal solution and study its characteristics. You can assume some things and come to a contradiction. This can prove your greedy strategy.