Kuber's blog

By Kuber, history, 2 months ago, In English

I'm solving 50 problems at each level. Recently I moved up to 1500 rated problems. I realize that the problems in this level are significantly different from 1400 rated problems topic wise. Till 1400, problems could be done by vectors mostly, but now, there's dp and trees.

Can anyone share with me if there is any theory I must read to get through this level or should I just learn the concepts through editorials of the problems that come forth?

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Basics first. You obviously should have an idea on how the algorithm/methodology works prior to usage. The ideas for its usage are usually learnt from competing in rounds. Regardless of whether you gain ratings or not, it should be clear that its always a gain for your experience and ideas. It could, in other words, be said that you learn what works in what situation (in generic terms) and what does not from competitions.

So IMO, you should learn the basics of the algorithms, and then come back to understand how the ideas in the editorials work (or how you worked it out in the competitions!)

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

    I know the basics of the algorithms. I've done some amount of reading and implementation, not thoroughly though. An alternative thought that I am considering, given that I am self taught is that I would think of a new algorithm only when I exhaust the available tools. For instance I have spent two hours on problems and solved them using stack only to learn that I'm missing out an edge case. And then, the editorials suggest that it was a dp problem and can be solved with 4 lines of code. Thereafter the use case of dp becomes very clear to me. This was just sharing some context on why I started the discussion.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Assuming you read a basic algorithm book (say, introduction to algorithms) and you know very basic combinatorics, number theory, and group theory, perhaps you just need to learn segment trees. Then you are good to solve any problem for div2. You don't need to study a lot; it's more about problem solving skills/abilities.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you. Your answer is very encouraging. This is exactly the kind of guidance I was seeking when I had posted the question.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Are there any solutions for improving the problem solving skill , right now especially in current rounds I suffer a lot from not being able to solve greedy/ad-hoc problems and I think I desperetaly need to improve my problem solving ability.