kayak's blog

Some questions about Informatics Olympiad preparation
By kayak, history, 6 years ago, In English

Hello Codeforces, I'm new to competitive programming (that's I know basic c++ syntax and basic algorithms like what's in first half of "Algorithm Design"). I have a bit of math contest background (nothing good, I couldn't even make to national MO camp. Just saying this because I know a bit of combinatorics/number theory so I don't need to relearn the basic combinatorics again for OI). I have a few questions:

  1. Are Codeforces problems good for practice? Which other judges/contests (eg: COCI) other than USACO are good for OI practice, and where I can find the judge for submission and official editorials ? For USACO, is there some places where I can read the alternative solutions to a problem rather than the ones mentioned in the official editorial?

  2. While learning some C++ libraries (eg STL), should I practice implementing the features myself before learning them ? Also, which sites are good for learning the standard libraries used in OI ? I tried bunch of USACO problems, and silver ones looked easy and platinum ones looked too hard and requiring a decent algorithmic knowledge, and gold seems to be fit (hard but not too hard) for my purposes now but I don't have good implementation skills and knowledge of C++ libraries (eg idk any of <bits>/<algorithm>/<stlib>) required to code the problems.

  3. For learning algorithms, which are better: online blogs or CLRS or other books (eg CP3)? I find the contents in CLRS to be interesting and fun to read but I read in Quora that it's useless and waste of time to learn stuff from CLRS for OI (Also it doesn't provide implementation). I also have CP3 by Halim and Halim but the major problem is that there are huge amount of problems and they're not sorted by difficulty so I fear I may waste a huge chunk of my time solving easy problems and not improving. I also read some criticism for it for being not very good, is this book good or are there any other book better for learning intermediate algorithms/data structures ?

  4. I don't like to work on easy problems (which takes less than thirty minutes), and I prefer to learn algorithms more from solving problems which requires that algorithm and failing to solve them and then learning the algorithms figuring out how I could come up with it rather than learning them beforehand. This takes a twice or more time rather than learning algorithms normally, but I think this is better for practice and building intuition. Is this strategy OK, or should I do it in the reverse way?

Sorry for making this post long. Thanks.

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

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Regarding CP3, it is a good book — I am one of its readers. I agree that there are a massive amount of problems in the book. A good way to use CP3 is to utilize uhunt which has topical and difficulty classification of problems in CP3. I would suggest using the book to learn new tricks (esp. for classical problems such as coin change and knuth-yao dp optimization).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it
  1. Codeforces has high quality contests and problems, but they lack an important aspect of IOI-style tasks: the problems don't have subtasks. You could try to upsolve some old IOI tasks or problems from IOI-style regional contests (for example CEOI and BOI) to get a hang of subtasks. They're important since they allow you to get some points even if you don't manage to solve the problem completely, and in IOI every point matters.
  2. In my opinion you should understand the general ideas of different STL data structures, especially their advantages and limitations, and know when to use them. However, you don't usually have to implement them by yourself in a contest setting. There are some important data structures that aren't in STL, such as segment tree — spend your time mastering those instead. Check out the book I linked for reference.
  3. I'd suggest you to read Competitive Programmer's Handbook by pllk: I think it's quite a clear and thorough introduction to competitive programming. The book is especially intended for people practicing for IOI.
  4. That's a good approach if it helps you understand the algorithm better. In the best case you might come up with the algorithm by yourself. It's always better to try to truly understand things instead of memorizing them: you can't apply your knowledge without a good understanding, and quickly memorized things are forgotten just as quickly.

Good luck!

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

    Thanks. The book you linked looks way better than CP3 — do you recommend any judge to supplement the theory portion of the book with problems?

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

how do u start in math contest and how can I prepare for it ?

→ Reply