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 $\to$ 2000)
• DMOJ → Codeforces conversion (x100 + 500)
• LeetCode (weekly contests. Goal: Top 1%)

Sources of Knowledge

• Competitive Programmer’s Handbook
• cp-algorithms.com
• USACO Guide (though I personally haven’t used that much)
• YouTubers: Colin Galen, Errichto, Algorithms Live
• Mathematics for Computer Science by MIT → helpful
• https://github.com/The-CODE-Plus-Plus-Community/Competitive-Programming-and-DSA/blob/main/ROADMAP.md

How to learn / practice

• What is practice/How to practice? (Help) on codeforces
  • Found link to this Seniors - Hard Level Problems: Investigation → really good set of tips
• How to practice Competitive programming by Um_nik
  • In archives you learn how to solve problems, in contests you learn how to do it fast
• How to Effectively Practice CP + Problem Solving Guide By SuperJ6
  • Really helpful footnotes!!
  • “find a rating range where you can solve around ~30-40% of the time on your own, and just grind down the problem set tab in reverse order of id (the default sorting)”

Guides for when you hit a plateau / lose motivation:

• you can do it, too! Codeforces blog
• Self-deception: maybe why you’re still grey after practicing every day

How to improve

Umnik talks about most of the time, you either know it or you don’t know it. It’s really hard to figure out in real-time a solution. Because as I’ve reflected myself, for a given problem, you either know the idea, or you don’t know the idea.

Therefore, you need to focus most of your energy on upsolving - solving problems that you usually can’t solve.

Three core skills for CP

• Having your mind be able to come up with ideas quickly
• Have your mind validate ideas quickly (and)
• Implement those ideas quickly

So how to improve? Do Metacognition, evaluate your own thought processes, and think, what could I have done to make sure I can come up with the solution?

• shoutout to Colin Galen for the tip

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 (2023-01-31)

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.

(2023-03-07) Okay, I am slowly getting back into the groove of problem-solving. 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.

• Training CP through pattern recognition is really bad. What you want to train is reasoning. Pattern recognition can lead to incorrect solutions.

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 single-handedly the best exercise for your brain to do problem-solving skills.

CP generalizes really well (William also 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.

2024-01-25: 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.

• NO. Sure, there is part of it, but you actually need to do reasoning too. Else, how do you know your solution is correct? You need to inference

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
  • Convex Hull DP
  • Bitmask DP
• 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 the set 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(\log n)$. 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 or long int. I tried to store an integer value outside the range of the type.
• https://whimsical.com/codeforces-candidate-master-roadmap-by-love-babbar-CiXPPD3CnwoXPr2d8Ajx1h

Topics

• Data Structure
• Dynamic Programming
• Binary Search
  • Ternary Search
• Graph Theory
• Tree Traversal
• Merge Intervals
• Flows and Cuts

math

• Chicken McNugget Theorem

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(n\log n)$ 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.