TheScrasse's blog

Competitive Programming Roadmap (target: [gray, blue])
By TheScrasse, history, 23 months ago, In English

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 problemset 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 also require ad-hoc ideas or twists to standard ideas.
  • The statements are short, and they require no "unnecessary" implementation details. Try to make your implementation as simple and short as possible.
  • The problems are split into topics. However, sections $$$5$$$ and $$$6$$$ contain "summary problems" with no topic, so that you don't get used to solve problems knowing the topic in advance.
  • The roadmap includes problems with various levels of difficulty, indicated by the number of stars (from $$$0$$$ to $$$6$$$).
  • If you are stuck on a problem for a long time, you may want to read the solution sketch at the end of the document. These sketches are written in such a way that only new ideas (= not used in the previous problems in the roadmap) are highlighted. So, you may want to think again about the problem. If you are still stuck, you may want to read the editorial (available on Codeforces and AtCoder). Of course, you shouldn't always use the solution sketch or the editorial. Ideally, you should use the solution sketch in less than half of the problems above your level, and read the complete editorial few times. However, reading the solution sketch and the editorial after solving the problem is often useful, as they can contain tips, alternative solutions or variants of the problem.

Then?

After finishing the roadmap (excluding the "Final problems" in section $$$14$$$), probably you have built a small "database" of standard-ish problems in your head and you're much better in the "what to think" part. "How to think" is more complex and it requires more time / experience to be mastered. Anyway, there are many ways to make further progress.

  • If you want to practice on a specific topic, you can use USACO Guide, or try the "bonus mashups" in the last section.
  • You can try harder problems on the Codeforces problemset (guessing from the samples doesn't work on harder problems) and on AtCoder problemset (they are not "impossible" anymore, since you know more tools to solve them).

Conclusion

Of course, feedback / suggestions / corrections are welcome. The roadmap may contain a lot of typos or the solutions may be unclear, let me know and I will try to fix.

If you're starting the roadmap, good luck! I hope it will be useful.

  • Vote: I like it
  • +283
  • Vote: I do not like it

Comments Comments (36)
| Write comment?
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

However, most of them are "trivial" if you already know the underlying idea and "impossible" otherwise.

Are you talking about AtCoder Beginner Contests' problems or AtCoder in general?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I'm talking about Atcoder Beginner Contest, especially problems D-F. ARC problems are much more ad-hoc and based on "how to think", ABC G-H may require more ideas.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let's analyse the last 2 ABCs

      Last ABC: D needs sieve, so ig its agrees with your definition, however most participants shud be knowing sieve. E needs no previous knowledge other than knowing how to write dfs F needs string hashing agreed

      Last to last ABC: D needs no knowledge, can be done with stack but i solved without by just simulating E needs no knowledge either unless you count knowing what dp is as knowledge F need segtree agreed, however it doesnt become trivial just by knowing segtree

      In these 6 problems, exactly one is trivial if you know the concept and 3-4 need no actual knowledge prerequisite.

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        Good point. Personally, I find few problems H from ABC somewhat "trivial", and I find the others much harder, so I thought the situation was even "worse" for easier but standard-ish problems such as D-F.

        For example, I think abc283_f is "trivial" if you've already seen that the idea "if there is $$$|i-j|$$$, split into $$$i < j$$$ and $$$i \geq j$$$" is very powerful. If a contestant comes up with it during the contest, there is a high chance he doesn't realize that a BIT solves the problem in the next 5 minutes, then he discards the idea.

        I'm interested in opinions by lower rated people. How do you find problems D-F? If you don't solve them, how often do you manage to learn something from them anyway (for example, by reading the editorial)?

        → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For me personally, abc D-F can vary a lot. Using examples from recent abcs there are tasks such as abc280_d which i have seen variations of many times and tasks such as abc283_e where it was pretty unique to anything i've solved before. If it is a problem similar to a problem i've solved before, I really don't learn much from the problem. However if a problem uses something that I'm not so familiar with, abcs are a great way to learn these. Overall, I am happy with abcs, they either teach me something new or refresh me on something i already know (usually it is 50/50).

          → Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

peltorator being orz

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This might just be me, but is anyone else getting a 502 Bad Gateway error?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I've updated the link.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

      → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry to post at this time(just finished an "unranted" round),but could you please find a way to make it accessible to Chinese users?At least on some net other than Google.As I know almost every google net is unaccessible in China totally. If possible,then thanks. P.S.About VPNs...If anyone can provide a reliable way,it also solves this.Thanks too if possible.

      → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain this in short?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are two types of problems First teach you what to think, Second requires you to think This roadmap contains these problems split on different topics and levels

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I cannot open the roadmap file, there is an error while I trying to open it.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome work. Really loved your mashups. Please make a master roadmap( and more mashups if you feel making other roadmap is a useless idea or so).I feel solving atcoder 600 rated problems is extremely hard. Can you make a post regarding what to study and where to practice list for that.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is awesome! I agree CodeForces is difficult for beginners. It's worthwhile to learn how to solve many standard problems (which can be found in the sources you listed or even old EDU contests on CodeForces). The truth is many CodeForces problems can be reduced with some observation to these more "standard" problems.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What star problems do you recommend me to start solving? Should I start solving all the problems?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try with 3/4 stars. If you can solve them, go the next problems in the same section.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you for this roadmap helped a lot,

Do you have a collection of ad-hoc or greedy problems for practice? I mostly struggle in those problems

→ Reply
»
16 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I'm an absolute beginner and thank you so much for this. These will be pretty much my first steps.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Found this right after hard-failing your previous round, what a coincidence, lol

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much, appreciated.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you dude!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why almost all of the problems are from Atcoder? what's behind that?

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

TheScrasse ... Hmm I lost my previous account but you can check my account ,

I started cp about 30 month ago and solved about 600 problem but I don't feel like I'm improving
I can solve div2 (A and B) and alwasy stuck in C
So I want to know How to determine my level and what should I solve from the problem set ( you provided or cf problem set )

And thanks

→ Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

TheScrasse give a blue to yellow roadmap please

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The problems are split into topics. However, sections 5 and 6 contain "summary problems" with no topic, so that you don't get used to solve problems knowing the topic in advance.

i thought they were a practice on prefix sum , but why they are not at the end and after all the topics however they are before DP & graphs? TheScrasse

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Following this, hope to get blue

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is ad hoc/non standard problems? can someone explain. also could anyone send a list to practise

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can you please update/repost the doc. https://drive.google.com/file/d/16Jydn250Ue7K7hOfzLxw4p5jFF4ZCqWT/view?usp=sharing

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Helpful, thanks.

→ Reply