Due to the installation of a new fire alarm in ITMO server room, the system may be occasionally unavailable on the 27-th of May between 06:00 and 15:00 (UTC). ×

robot-dreams's blog

By robot-dreams, history, 4 weeks ago, In English,

I'm interested in improving efficiently, and the main advice I see (on blogs, comments, CP Discord, etc.) is "solve more problems". For someone who's not solving any problems yet, this is great advice. Additional detail seems unhelpful because getting started is WAY more important than nitpicking and prematurely worrying about efficiency.

But how can someone who's already solving a lot of problems improve more efficiently?

I have a lot of unanswered questions about this:

How should we choose problem difficulties?

Someone who's already Expert probably won't get to the next level by solving 500 problems that are all Div2A. I often hear "solve problems that are slightly above your current level", and once again this is great advice. But it's important to sometimes mix in "easy" problems for practicing speed and staying motivated. How should we balance the two?

How should we choose problem topics?

I've heard arguments for choosing problems randomly, but it makes sense to sometimes choose specific topics to address weak points or review important concepts. When should we do one or the other?

How should we structure our training schedules?

My friend who does competitive gymnastics said that his training schedule goes "Hard, Hard, Easy" (two sessions of intense training followed by one session of lighter training, to help with recovery). How should competitive programmers structure their training schedules?

What should we do after getting AC?

One way is to just move on to the next problem. But Polya's book "How to Solve It" talks about four steps in problem solving: understand the problem, make a plan, carry out the plan, and look back. What are good ways to do "look back" so we can get the most out of each problem?

What other activities should we do?

Obviously, there's participating in contests. But besides that, is it helpful to read textbooks? Prove theorems? Watch streams? Play Zachtronics games? How helpful are these activities compared to only solving problems? How should we divide our time between these different activities?

I know there's no single answer to these questions that works for everybody in every situation, but I'm still interested in hearing your ideas.

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

»
4 weeks ago, # |
  Vote: I like it +61 Vote: I do not like it

Maybe another question that you can add is whether to solve individual problems or to do full timed contests.

»
4 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

I think its very easy to do better. Just watch more twice. Duh

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

The way that I've trained so far is split into two modes: contest mode and learning mode.

First thing is it makes sense to practice like you compete: contests. I consider there to be three stages to a contest: during, upsolving, and retrospective. First you do the contest and solve the problems you know how to. Next you go read editorials and solve the problems with help. Finally, you look back, say "why could I not solve this problem?", and fix it if you can.

That brings you to the learning mode. When you encounter an algorithm you didn't know before you need to practice it to be able to use it. If you practice by finding problems that use the algorithm and solving them it will teach you how to recognize it as well as how it works. Both are important. I usually write it 3-4 times from scratch to make sure I understand it well.

All that said, I think that competitive programming is unique in how it mixes talent and practice. Even if you are practicing the best way you can, there may be people who improve much faster than you do. Don't let this stop you.

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

The idea below should help CM or M (maybe expert too) level participants reach IM or GM.

In my opinion, the easiest way to improve is to first find the topics you are weak at. This can be done by either looking at some recent contests you have done, or by doing a couple of VC. You should be able to see some types of problems you are troubled with.

Well now you have a topic you are weak at or you dislike (I'll assume it's one of the CF tags). One way to improve on it, is by simply opening the "Problemset page", choosing the tag, sorting the problems by difficulty and starting to solve them in order. This process isn't bad, but it requires a lot of time and also you solve a lot of problems that might be easy for you.

What I did (and I think it's one of the fastest ways to improve on a certain topic) is the following:

Again we will sort the problems, but we will start from ones that are quite hard for us. When I did this there were no difficulties, but as we have them now, I think by starting from problems with difficulty equal to ("Your rating" + 200), you will be solving problem that will be quite hard for you. So far the process is the same as a lot of tips you might have read in other blogs for training suggestions. The difference comes when we look at the way we solve the problems.

Most of the times when I solve a problem to train on a certain topic, I will spend no more than 10 minutes before I look at the solution. That's because if I have been thinking for 10 minutes straight, probably there is a concept I don't know or there is an observation I'm missing. And as you are training it is better to solve more problems (you will learn more "tricks" and ideas). So you should look at the editorial after 10 minutes.

If in the editorial there is a concept you aren't familiar with, learn it and find one or two problems related to it (you can easily find them by googling). If you know everything from this editorial, you probably now know the observation(s) you were missing. Remember them so next time you won't miss them (generally in CP I have noticed that there are a lot of problems which are just a combination of such observations). Well finally you can implement the problem. If it isn't hard to implement or you have implemented such a thing recently you might choose to not code it because probably it won't be very beneficial for you.

The whole process of solving one problem will be 30-40 minutes if you couldn't initially solve the problem or about 20 minutes if you were able to solve it. Imagine you train for 1 hour/day. This means you should be able to solve 2 problems/day. To get confident in a topic, I think solving 10-15 problems is enough to learn the most common ideas and tricks. This means that a week or two are enough for one tag. If you spend more time every day, it will be even faster.

Obviously there is a limited number of topics you are bad at. So if you are serious, in two or three months you will be good at the majority of them. Now to be able to increase your level, you should train on one of the following:

1) Finding observations on problems faster

2) Implementing the problems faster

I'm not exactly sure how to train on the latter, but my guess is by simply solving more problems and implementing all of them will be sufficient. On the other hand, I know how to improve on the former. If you train on constructive problems ("constructive algorithms" tag on CF) you will significantly improve the time you spend on finding observations. Solving some math problems or reading the posts for the combinatorics tag on AoPS also improves that. Finally solving some problems from OIs can also be helpful, as those problems tend to have a lot of observations that are connected to each other and also because of the subtasks the process of finding them is easier.

Also something useful is to do the CF rounds ( when you can and CF holds them at a nice time :') ) or do virtual contests on them.

So in conclusion, you should find the topics you are weak at and then improve on them. After this. After this, train you observation finding skills and implementation time. This is the general way I have trained for the last two years and it worked for me. I hope some of you will find this useful.

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

    For ad-hoc problems (and also those requiring observation), which gets more prevalent in the more difficult problems, do you think one should spend more time thinking about them before reading tutorials?

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

      So when I trained on ad-hoc I again spent about 10 minutes on thinking, unless the problem was from an OI (APIO, BOI or IOI). On these problems I spent an hour or so because they involve more observations.

      Also something I forgot to mention in the comment above. After I had a training session, I always read a significantly harder problem and I was thinking on it in the background. For example when I was travelling to school, washing dishes and etc. Then at the beginning of the next session I read the solution (if I still didn't know how to solve it).

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

    Very good advices, but read editorial after 10 minutes of thinking is it improve our thinking abilities if we know algorithms that may be used in this problem? It looks like remember solutions for problems, and also what to do if there is no editorial for problem because lot of OJs have not this. Sorry for my bad english and thank you for share your strategy.

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

      Well the reason I think reading the editorial after 10 minutes is sufficient is because you do this for topics you are weak at. If you don't know the main ideas that are used for such problems, what is the point of wasting your time?

      You may find it fulfilling to come up with one of these ideas yourself, but you will spend more time on this and in the long run I don't think it will be very useful.

      At least in my experience, 10 minutes of thinking still improves your thinking abilities as you learn the direction in which you must think when solving problems on a certain topic.

      About the OI problems. You are right that there are a lot of them without tutorials, but there is oj.uz (<3) which has the majority of OI problems. You can find a clear written code in the submissions there (sometimes there are even comments on what is the idea). So not having an editorial isn't a problem.

      Btw when focusing on OI problems I suggest checking out the JOI spring camp as the problems there are of high quality (unfortunately there are English statements only for 2017, 2018 and 2019).

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

    I train for 3-4 hrs every day on 1900-2300 problems, if I don't get a problem I don't look at editorial for atleast a day, 70-80% of the problems I come up with solution by then, compared to 30% success rate in first 10 minutes. It's so satisfying to do that instead of looking at solution, do you think it's hindering for my rating growth?

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

      Well you should try training like I described for some time (for example a week or two) and see if it works for you. I think you will be satisfied with the results as you will learn more new ideas, but the process of training probably won't be that satisfying.

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

    By "Your rating", do you mean my current rating or my max. rating? Also, thank you very much for such a detailed comment.

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

      Well you should check. If "your rating" + 200 problems are quite hard for you, go with them. Else I suggest you go with "max rating".

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

    Well, probably reading editorials is a good idea. I almost never check/pay attention to them, even after on-site contests. It is common for me to think about a problem for a long time, more than a week, because I really want to come up with the solution myself, without any kind of hints from outside.

    In the end, my performance is very unstable: sometimes I can solve hard problems, but other times I am unable to solve some stupid shit, while everyone else get it quickly.

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

    Well thanks for sharing those things... yet one of the question I feel which was very valid asked by the author was : How to extract maximum from a problem in which one just received AC ( Author asks this as : What should we do after getting AC? )

    Could you throw some light on this as well @radoslav11... It would prove very helpful...

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Spaced repetition. In other words, revision.

  2. Solve problems outside CP. It will give more insights and make you more intelligent overall.

  3. Try to solve a problem with different techniques, even the bad ones. The goal of this is to learn to apply techniques in unusual ways. This is actually controversial, and generally not useful, but I've seen problems being solved with completely unrelated approaches, and it would be great If I can come up with these unrelated approaches rather than reading about someone else coming up with these variants. We know that usually a problem can be solved with multiple techniques, yet we generally solve with one and delegate finding other approaches to the contest and editorial comment section. "I'll read the blog to see if there are other approaches". Well, since there is a high possibility of that being true, first try to find 2 other approaches yourself.

  4. Try to understand why you couldn't solve something. What stopped you from succeeding. I also happen to play chess, and so I read a bit about my heroes, and the reason Bobby Fischer was so dangerous over the board, than all others in his time is not because he wanted to know why someone won, but because he was more interested to know why someone lost.

»
4 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

Definitely Zachtronics games.

»
4 weeks ago, # |
  Vote: I like it +57 Vote: I do not like it

radoslav11 pointed out that in order for one to get 2300~2400, the most important thing is to keep learning about algorithms/ideas/trick. That's why he said that we should look at the tutorials in ten minutes.

For me I think ten minutes might not be enough. Sometimes I read about the tutorial in ten minutes and found out that the idea is not that hard and I could have solved it with things I've learnt before. I'd say the process of "trying to solve a problem" is also important since it is exactly what we need to do in a contest.

One supporting view from E869120's blog along with TozanSoutherpacks's comment is that one should not never look at the tutorial before one solved the problem.

I suggest setting a dividing line here: For problem of difficulty $$$\leq 2200$$$, one can look at the tutorial after 10 minutes since a large part of the problems are related to some common tricks. For problems of larger difficulty (,say, $$$\geq 2300$$$), one should at least try for a longer time to think about them since we want to train our instinct on hard problems. (We will spend a longer time in a problem for sure, but we might benefit from that in long run.)

For me, I am not sure that my last point (for $$$\geq 2300$$$) is suitable for everyone. I am also trying to figure out whether it will work for me (I will also try radoslav11's method). Let's wait and see.

»
4 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

One thing that I have found to be very helpful is to look at submissions of people who solved problems very fast. Editorial is good for getting an idea, but I am constantly impressed by the simplicity of the top participants code. Some people have very bad code with lots of #DEFINE lines and bad variable names it's pretty much unreadable, so you might have to check a few people before you find someone good. But you will often see ideas on how to implement something efficiently that the editorial won't show you.