← Back to context

Comment by novok

5 years ago

What are the 'chunks' of competitive programming? Like knowing how to make a graph, use hash tables / arrays well, a typical dynamic programming solution and so on?

No, its mostly how to structure the full computation flow for different things. If there were an easy set of patterns then it would already be in some book, these things are skills you can't put in a book.

For example, when is it useful to create a function instead of writing the code inline? Many times the amount of code grows exponentially with problem size unless you properly create good functions, so you need to learn to get good at that. Code reuse also greatly improves how fast you can write the solution and reduces bugs, so it is good even when it isn't absolutely necessary.

Where should the data be, who should own what data, how is the data supposed to be found where you need it? And so on. Many problems requires you to create quite elaborate data structures and relationships, finding the right data in a reasonable amount of time is one of the hardest problems to solve even in competitive programming.

Caching and lazy computations as well, it is used everywhere in competitive programming. The fastest solution is where you don't do anything at all, so you get good at understanding how and when to cache results, when to throw out caches in order to handle new data etc.

Writing proper tests, since you get no credit if your code fails for any case you need to write tests that stresses all parts of the code you are unsure about. This teaches you to get really good about understanding the weaknesses in the code you write, debugging and creating solutions that are bug free.

Stuff like that is really important to get good at competitive programming, you need to be able to get good answer those questions in minutes for complex problems if you want to compete with the best in the world. Now you might notice that many basic data structures and algorithms are just solutions to the above problems, the point is to learn many generic cases of the above so you can compose your own data structures and algorithms as everyone of the harder problems requires you to do that.

And as you can realize these things are very useful for any sort of program, not just competitive programming. Managing data layouts and when it is useful to create functions is the majority of normal programming, if you can do those really quickly then there isn't much left that will take time.

Now, the bad rep competitive programming has is mostly that people just do the easy problems that can be summarized as "implement this basic algorithm". Real competitive programming isn't like that at all. Of course you need to be able to do the simple algorithms, but knowing how to implement the algorithms is just table stakes.

"Don't I practice these things when writing normal programs?"

Not in the same way. Competitive programming is about doing these in their pure form. In normal programming there are so many other things that it is hard to focus on the code, while in competitive programming all you have is code and then a really good test suite you can do to verify your solution once you think you are done. This way you practice a huge range of programming chunks really quickly, compared to trying to test them out and learn them in real world codebases.

Edit: Btw, last time I checked Leetcode didn't have many questions that stresses these important points, its mostly just useful to learn algorithms used in these interviews, it isn't good to learn programming. There are many good competitive programming sites to use instead. Leetcode is good if you want to pass interviews with minimal effort right now, but it isn't good if you want to get good. Also you just get good at chunks, you will still need to practice writing and structuring larger programs and solutions. But practicing that is way easier when you have mastered these chunks.

  • Out of curiosity. What would be the best way to learn these skills in your opinion? What are these "many good competitive programming sites" that you recommend?

    • The site I used is codeforces.

      https://codeforces.com/?f0a28=1

      It has the widest selection and types of problems as far as I know but that was a while ago. It runs competitions all the time, the problem descriptions are well defined unlike leetcode which often misses a lot of requirements, it has way more kinds of problems than topcoder, you can test yourself against old competitions as if they ran real time to properly ensure you don't take too much time or accidentally cheat etc.

      > What would be the best way to learn these skills in your opinion?

      I think today it is hard to practice without competitive programming. Ideally someone would make a similar format pushing your limits like this but without so much focus on complex algorithms and maths, but since that doesn't exist competitive programming is what we are left with. The competition aspect is really important since it is how people push each others limits. It is easy to think "you can't get much better than this" when you just sit and code by yourself, but in programming competitions you see how fast and accurately others can solve problems, so you realize that you could get just as fast and accurate with a bit of practice.

      And no, it is not memorization. Consider this easy problem which mediocre competitive programmer manages to solve but those below mediocre fails at (we can see that from how well people did on it in the competition):

      https://codeforces.com/contest/1496/problem/B

      There is no algorithm you have to know for that, it is just good old logic and some coding. It is really easy and I could solve in in a few minutes even my todays rusty self, but you can't memorize solutions to such problems, you just have to be fast both with the reasoning and the code. Note "mex" is not a standard term, it is just something they made up for that problem.

      1 reply →