Competitive Programming Roadmap (target: [gray, blue])

Правка en4, от TheScrasse, 2023-01-07 18:56:28

tl;dr

  • Competitive programming roadmap here.
  • It should be suitable both for newcomers and for people with some experience with CP: let's say, up to blue on Codeforces.
  • It contains ~ 100 "must-know" problems about various topics: ad-hoc, STL, binary search, DP, number theory, graphs.
  • There are solution sketches at the bottom, don't feel guilty reading them if stuck.

Why?

Many people new to Codeforces seek advice about how to get better / which problems to try. Other people are stuck on gray / green even after solving a lot of problems. This roadmap aims to be a solution.

My take: to be good at competitive programming, you have to know "what to think" and "how to think" when you try a problem.

  • "What to think": you have to know a decent amount of standard problems / techniques. Sometimes, a problem requires steps / observations that seem obvious if you've already seen them. Other times, you may solve a problem by reducing it to a well-known sub-problem. On the other hand, you may realize you've done something wrong if you "reduce" the problem to something that you know it's unsolvable under the given constraints. All this isn't possible if you don't know those standard problems.
  • "How to think": it comes down to "building" a path to the solution. Sometimes, you need to find new insights / observations by analyzing the process in the statement, manipulating math equations, etc. Other times, you need to find a twist to a well-known technique. You can practice "how to think" by solving ad-hoc / non-standard problems.

So, how to practice?

  • Using the Codeforces problemset is quite good for experienced people, but it may turn out to be harmful for beginners. Surely, recent contests on Codeforces have a very good quality, and even the easiest problems are often original and can't be googled. However, this means there are no easy standard problems, so you don't really improve in "what to think" when you solve them.
    Also, even the easiest problems are supposed to require an "idea" that often turns out to be nontrivial to find / prove without looking at the sample input / output. So, in most cases, the most convenient way to solve easy problems is to find a pattern in the samples, and this does not actually teach you "how to think" to solve harder problems. For example, in problem 1768A - Greatest Convex it's way easier to observe that the solution is $$$k-1$$$ from the samples than to actually find it out. (Note: this doesn't mean it's a bad problem, but only practicing with this kind of problems may be a bad practice).
  • CSES mainly contains standard problems, so it doesn't really teach "how to think".
  • AtCoder contains a lot of educational problems, and AtCoder Beginner Contests problems are quite good for practice. However, most of them are "trivial" if you already know the underlying idea and "impossible" otherwise.
  • USACO Guide is very good, but it's more oriented to OI (Olympiads in Informatics) and it contains some problems with very long statements and where the bottleneck is the implementation.

How does the roadmap work?

The roadmap contains ~ 100 problems, mainly from AtCoder, Codeforces and an Italian online judge.

  • "What to think": the problems are "standard-ish", and they cover most of the ideas required in problems ranging from easy (div2A) to medium (div2D-E). In other words, given a problem of such difficulty, there is a high chance it has at least one idea in common with a problem in the roadmap.
  • "How to think": the problems are "not so standard", and most of them require ad-hoc ideas or twists to standard ideas.
  • The statements are short, and they require no "unnecessary" implementation details.
Теги roadmap, beginner

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en16 Английский TheScrasse 2023-01-24 20:10:21 0 (published)
en15 Английский TheScrasse 2023-01-24 20:10:11 0 (saved to drafts)
en14 Английский TheScrasse 2023-01-08 23:45:51 80
en13 Английский TheScrasse 2023-01-08 13:17:54 0 (published)
en12 Английский TheScrasse 2023-01-08 04:02:51 0 (saved to drafts)
en11 Английский TheScrasse 2023-01-07 20:06:17 0 (published)
en10 Английский TheScrasse 2023-01-07 19:32:26 275
en9 Английский TheScrasse 2023-01-07 19:28:39 240
en8 Английский TheScrasse 2023-01-07 19:26:11 4
en7 Английский TheScrasse 2023-01-07 19:25:47 334
en6 Английский TheScrasse 2023-01-07 19:20:41 701
en5 Английский TheScrasse 2023-01-07 19:13:38 759 Tiny change: 'ars (from 0 to 6).' -> 'ars (from $0$ to $6$).'
en4 Английский TheScrasse 2023-01-07 18:56:28 510
en3 Английский TheScrasse 2023-01-07 18:38:22 1365
en2 Английский TheScrasse 2023-01-07 18:18:58 1881 Tiny change: 'y, graphs. - There ar' -> 'y, graphs.\n- There ar'
en1 Английский TheScrasse 2023-01-07 17:38:14 493 Initial revision (saved to drafts)