turzo_sawroop's blog

By turzo_sawroop, history, 5 weeks ago, In English

Actually I wanna be an Expert.Now-a-days I have started solving 2-3 problems in div-2 contests consistently.I believe with little more consistency and speed I will reach expert soon.In my university my cp community is teaching very unusual topics like heavy light decomposition,lca and so on.But are they really necessary to reach expert or cm??Because I am very comfortable solving A,B,C without knowing all these.How much topic knowledge do I need to have to be expert or cm??

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

»
5 weeks ago, # |
Rev. 4   Vote: I like it +6 Vote: I do not like it

In order to reach Expert or CM (hopefully I will reach CM soon) you don't need any of those. A, B, C, D usually requires simple algorithms and smart observations.

Yet, learning more algorithms will only help you.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Yes I also felt the same way but got confused.Also in practice while solving D I never faced any type of unusual algorithms.A friend of mine just said that Knowing more topics means you have more nodes in your head but without extra-ordinary thinking skills those nodes aren't connected with edges.I think he's right.

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

      It takes either extraordinary thinking skills or experience to create edges between the nodes. That's why the best advice for cp is just to practice. Although you should practice problems a bit harder than your rating to connect the nodes with lowest degree.

»
5 weeks ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it

Despite the current trends in cp away from common algorithms/topics and towards olympiad math style combinatorial processes*, I am still a huge fan of learning algorithms for their thought processes.

To make CM, the only topic techniques you probably need to know are basic number theory and combinatorics, binary search, dfs/bfs, and how to apply to dp and combine it with previously mentioned topics. The main other thing to practice is just learning how to come up with greedy processes in different scenarios, and it is just a matter of seeing enough problems to get a feel for popular greedy techniques.

However, I think learning topics like lca and heavy light decomposition teach you important general cs techniques that you may end up applying in greedy processes anyway, such as those algorithms showing different ways how iterating over decreasing powers of two can be used to break up problems into log parts. The key is not just to memorize the algorithm, but really think about the underlying techniques. Plus, you never know when it might end up showing up in contest.

*actually the most recent cf rounds have had more dp and trees again starting around div2 C or D :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thank you so much.It's a great advice.Actually I love observing algorithms, it's not like that I don't.I have very keen interest in learning them in future as I wanna become a good computer scientist.But there is a big misconception among coders around me what to learn and what not to in-order to do well in cp.That's why I posted this so that there remains no confusion inside me and my friends.

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

    Can you suggest some resources for combinatorics? I always face difficulty when problems are based on combinatorics.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

well to reach expert you have to consistently solve around 3 problems (max rated about 1700). I dont think you need to have knowledge of lca or heavy light decompositon or game theory but a basic knowledge of dp as well as graph algorithms like MST and djisktra is essential. You could also learn a DS like segment tree if you want. Also a bit of no theory is also required (sieve, euclidean algo)

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Um_nik said "I reached master without knowing segment tree 7 years ago. Then I learned segment tree and got to red. It doesn't work the other way around though. If you can only apply data structures and standard algorithms you are not a good CPer."