rachit287's blog

What to study and learn as a beginner in Competitive Programming?
By rachit287, 5 years ago, In English

Hi, I am fairly new to the Competitive Programming journey, solving problems for little over a month.

A gist background : I enrolled in a boot-camp for DS and Algorithms, learnt the tricks and methodology, but was overwhelmed for a large portion of the course. I have an overview of it and some basic understanding, but that's about it. After completing the course, I switched over to Codeforces, Codechef and some other online CP sites.

I have been solving problems for a month now, sorted according to ratings, i.e. 400-700 and lately some of the problems with 800. After a while, I gave 3 contests, Educational Codeforces Round 84 (Rated for Div. 2) , March Long and Cook-off of Codechef as I wanted to have a real-time experience of how competitive programming goes about. I fared bad, obviously. Solved a question each in the Codechef contests, and couldn't even solve the first problem in Educational Codeforces Round 84 (Rated for Div. 2). Rating and failure doesn't bog me down, and it won't. But the problem I seem to have is of proper guidance and trajectory on which I can take action.

To make it more clear, here are the issues I am facing:

  1. What topics should I study to be able to solve A, B and C problems as of now?
  2. How many Type A problems to solve before switching to the problems with higher rating/increased difficulty?
  3. What techniques(DP, Greedy, Backtracking etc.) should I learn and try to use currently?
  4. Do I study basic Algebra like Euclidean/ Extended Euclidean algorithm , easier topics of Number Theory, and how important are they?
  5. When should I start with topics like Graph Theory, Disjoint Set Union and beyond?

I know these are a lot of questions, but these are some genuine problems I have been facing. Please cut me some slack as it is my first post, thanks!

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

Comments Comments (17)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

There is a very nice blog written by E869120. Go through the section "3-1. Practice Skills — From Rating 1000 to 1400" of this pdf.

Link of blog

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

For me, the most effective way of learning CP is by upsolving problems that you failed to solve in contest. There are editorials for that reason. If there are unfamiliar names (of algorithms/techniques/etc), google them. If you still don't understand the editorial, ask in the comment section. This is probably because when you failed to solve a problem, and knowing the solution later, it gets an adhesive upgrade that lets it stick to my head better (basically my chance of remembering it rises).

Alternatively, you can go to sites like https://projecteuler.net/ that doesn't require you to code, but still trains your logic. This site makes me realize that simply having paper and pen when solving cp problems is helpful.

Btw, answering your issues:

  1. I don't know. They're kinda random. Just solve some A,B,C problems and you can see that there's a lot to learn.
  2. zero. You can jump to solve B or C right away (probably).
  3. All of them. Some techniques require you to have some kind of instinct/experience that you develop from solving problems (especially greedy, otherwise you need to be a master of proving your own lemmas, which also requires experience). Therefore, it's good to know how the technique works first. Then, you can try solving related problems, failed at doing so, and be amazed that the technique can be used like that, etc etc.
  4. Yes you do. They are quite important. But just knowing is probably enough. Later down the road you might find how they can be used to solve some problems.
  5. Up to you. I learnt them pretty early, because the theory itself is interesting and easy enough compared to the implementation. You can read some blogs/tutorials/whatever right now and it will never be a problem.

You can also google something like codeforces starting out competitive programming if you haven't already.

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

    how many problems u have solved at projecteuler? just curious! tnx

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

      I don't remember. Probably 20 or so. I even forgot my username and password. But, it's still a good place to practice.

      I don't use projecteuler a lot because I had an alternative site. But it's in another language that is not english, so I cannot recommend that.

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

    Thanks, the answers to 1 and 2 are really helpful. I will jump right into solving B and C problems, which I was avoiding until now. Thanks again for helping out!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Dude, I think, First read about most of the commonly used algorithms in Contests.

      Like- DSU, DFS, BFS, Shortest Paths, Dynamic Programming etc.

      For that, I'd prefer https://cp-algorithms.com/

      It's a great resource. Don't judge it by it's UI. The resource is a gem. GOod luck and happy Learning

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

        Thanks, I have known about this site, was recommended by a good friend. Thanks for your input!

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For each of your issues:

  1. I suppose you meant D2A to D2C.
    First, the difficulty of A, B and C problems in different Div 2 contest is not always the same.
    For example, 630A is not very difficult to get the answer, but it is quite difficult to code than a usual Div2A. 632A is quite easy to code (just as many other Div2As), but it is quite difficult to get the answer.
    Solving a Div2A might also be hard for beginners, too.
    In my opinion, in order to solve most of the Div2As, you should know a bit of greedy (and how to proove it is correct), some math skills.
    If you want to solve most of the Div2Bs, you should learn bit of linear DP, strings, sortings, binary search and some basic graph theory knowledge (i.e. how to build a graph), and maybe some bitwise calculation will be helpful.
    If you want to solve most of the Div2Cs, you should learn DFS, BFS, DSU, etc.
  2. That depends on you. If you can solve some kinds of problems easily, then you might need some more difficult problems to exercise.
  3. The answer is in above.
  4. If you are studying in collage, they are very easy for you.
  5. I don't know.

Sorry for my poor English...

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

    Thanks, this helped a lot. Where can I practice good Greedy questions?

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

      Hmm...

      Is greedy questions in CodeForces not good enough?

      If you have a good translator or you can read Chinese, I recommend a CP website for beginners which is well-known in China: Luogu. There are some greedy questions there. There are lots of tutorials to help you if you can't solve some problems.

      However, I think greedy questions in CF is good enough.

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

    Would like to add to the first point... Data structures like vector, set, map, priority_queue, deque etc are quite important for implementation problems. Also Number theory problems related to gcd, lcm, modular arithmetic, primes, divisors, sieve etc are frequently asked.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure if this is going to help but- to answer all your problems, I would suggest simply spend some more time on whatever you're currently trying to do. With time you'll either realise whatever you're doing is working for you — where you should just keep doing so until it's not the case anymore; or you'll realise that you need a difference in strategy. I have experienced that I do find the solution to my own problems with time. And I personally felt uneasy when I tried to follow somebody else's workflow.

Otherwise, I suggest reading Errichto's FAQ blog where he answers questions like "How to get better at CP". He has also started a new series of videos to introduce people to CP on his youtube channel.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You should start by studying basic implementation, brute force and math (a lot of div2A's are math based). Once you get comfortable with that, look into binary search, two pointers, constructive algorithm questions. If you're wondering when you should move up the difficulty of your problems, it should be when you can solve the majority of the problem rating you're practicing at right now. Don't try to jump to dynamic programming or graphs etc. I tried that and it didn't get me anywhere. I've been solving ~1200 rated problems on the topics I'm weak at and I can already see improvement.

→ Reply