I_love_Hoang_Yen's blog

The 'science' of training in competitive programming
By I_love_Hoang_Yen, 9 years ago, In English

So few minutes ago I answered this question on Quora. It felt like a good answer (because it has pictures), so I would like to share it again here.

If you don't see the images, just click the Quora link above

Many people tell you that solving lots of problems and you will become red on Topcoder/Codeforces one day. It is true, and is the only universally approved way in competitive programming community, but actually it is just half of the story. Let me first explain to you the 'science' of problem solving (which is not very scientific, since it was only developed by myself).

For each problem, in order to solve it, you must jump over a gap. It can be either a difficult implementation, or some hard-to-see observation, or difficult algorithm, etc.

Image and video hosting by TinyPic

For me, some problems are very easy (e.g. Codeforces div 2 A, B..), because the gap feel so small to me, and passing through them feels just like casual walking.

Image and video hosting by TinyPic

Some problems are very hard. The gap is just too huge, or there are many many gaps, and you can get stuck in the middle because you're too tired after maybe first gap.

Image and video hosting by TinyPic

Using this science, we can explain a lot of phenomenon in the competitive programming world:

  • Some guys learn very fast, got to div 1 only after like a couple of weeks after he just started programming: Some people are born with high jumping ability (problem solving skill). They can jump over average gaps easily.
  • The more you train, the better you become: Of course, if you jump around all day, you must be somewhat better at jumping through gaps, and thus being able to solve more difficult problems in less time, since you don't need lots of mental preparation or warm up excercise before jumping.

But.. it also means that, if you just solve too easy problems, you can still only walk through small gaps. You may walk through gaps faster, but you are still unable to jump.

So yes, the best strategy to improve your competitive programming skill is to practice a lot, but you must solve gradually harder problems, not just the easy ones. Get out of your comfortable zone and challenge yourself. For example, if you solve problems on Codeforces:

  • Sort by number of people who solved it.
  • Start with page 1
  • Solve some problems. If you feel you can solve them in like 5-10 mins, immediately ignore the other problems, move on to page 2
  • Continue until you feel challenged (e.g. need like an hour to solve / can not solve at all / ...).
  • Try really hard, but if you fail, look at editorial, ask for solutions, ...
  • Vote: I like it
  • +563
  • Vote: I do not like it

Comments Comments (40)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The analogy with gaps makes sense. I wouldn't call it "science", though — it's just a way to view "practice makes perfect".

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Thanks, but I can't come up with better naming :(

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I need your suggestion/clarification

      I have always believed in solving lots of problem but your statement that "solve smart not lot" making me into trouble.I can't judge what to do now.As you can see my color is green and I am not so "genius" by birth so What i feel that is that it becomes necessary for peoples like me(not so smart) to solve lots of problem to become good in problem solving.After few years If i don't become red at least i will be purple by then which is Ok.If you do practise for years doesn't matter if you are born smart or not but you will certainly become smart.What do you think,Give your views please.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        there is no such thing as being "smart" or being an "idiot" all people have a thing their good at.

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

          I think "Practice" is American while "Practise" is British. Just like color and colour.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +42 Vote: I do not like it

            I was unable to refrain from posting that.

            → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            yes i think you're right i searched it and it had hits
            i'm sorry for being a "vocabulary nazi"(is this what it's called?) for the guy up there

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              It's grammar nazi, actually. Or, if you prefer

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                well it wasn't grammar so i said "vocabulary"

                → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +65 Vote: I do not like it

        "Hard problems" is subjective. A good rule of thumb for learning problem solving (at least according to me) is that your problem selection is good if you fail to solve roughly 50% of problems you attempt. Anything in [20%,80%] should still be fine, although many people have problems staying motivated if they fail too often. Read solutions for problems you fail to solve.

        (There is some actual math behind this. Hopefully one day I'll have the time to write it down.)

        Of course, at green a more immediate benefit will most likely come from practicing implementation skills.

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

          It would be great if you take out time to explain that math too .

          → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        What I do may help you. I try to practice a "hard" problem at first. After solving 1 hard problem, I solve 3/4 easy problems to give myself as a gift. :)

        Now, what is called "hard" and "easy"? In my way, a hard problem is a specific type of problem I never did before. Solving which I must have to go out of comfort zone. For example, if I didn't solve any BFS problem, that is hard for me.

        An easy problem is that type of problem I solved in the past regularly. Solving these increases my coding speed and accuracy.

        Hope it will help you. (Though I am not a genius and programmer regular)

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

      The better term is ACTIVATION ENERGY , mate

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +50 Vote: I do not like it

I think this is a good post and I agree with the main idea, however at least personally I would say there is still some value to solving simple problems, even if they are easy. To me it also helps build confidence, and allows one to practice doing things in the simplest way possible. For instance I think that many beginners can solve fairly easily the problems on the first page, however their solutions will be say 15-25 lines, where as red competitors on the same problems will always be <10. This might seem like meaningless difference in the easier problems, however if one tries to solve harder problems I think it becomes significant, because even if the beginner can come up with the right idea for the problem, their solution length might be 100+ lines, where as top people will be under 50, and therefore will have far fewer errors. So I think it is not enough to be able to solve the easy problems in 5-10 minutes, it is also important to be able to solve them concisely, and I think this is a skill that has to be practiced.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    Thanks. I can agree that solving easy problems do give motivation while still being able to learn something (it's wonderful to see the green Accepted). Personally I did solve all problems in first 300 most solved problems on Codeforces.

    Though, the original question author described that he just solved 50 easy problems at a time, and asked what would be the best method to improve in next 2-3 months, so I write this for specific purpose of replying to that (maybe it's better to have a good mixture of easy, medium & hard problems, similar to what happens in contests).

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

What to do if there is no proper idea for the task?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    As written in my last sentence: look at editorial, ask for solutions.

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

      If I haven't solved problem for 1-2 hours, what is better immediately look at editorial or try to solve it in 1-3 days?

      If I go first way, I would have more problems accepted, but I am not sure if I have great profit in solving tasks, only in coding. Of course I will be able to solve similar task in the future, but not more. And now, after such experience, I can say that during contest if I don't have any idea about easy enough task(>600 AC in Div.1) my brain panics and stop working.

      If I go second way, I can waste my time and as a result have unsolved problem and lack of confidence in the contest. But if finally I have AC, I feel great profit, I'm sure i'll solve the problem with the same idea or partially idea.

      So, the question is what is better number or quality of solved tasks?)

      Some "Red persons" advice to postponed task until you can solve it (But I don't see any profit of solving tasks you know how to solve).

      Sorry for my English :D

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Both quantity and quality matter.

        When you just start competitive programming, there're just too many tricks that you don't know. Even if you try for few days, it's likely that you won't have any progress. Usually it's either you solve it in 30mins — few hours, or you never solve it at all. So in these cases, it's better to read editorials than to waste your time. How long you try depends on how long you can focus. If you start looking out the windows, that is probably a sign that you can stop.

        As you earn more experience, you should spend more and more time thinking about problems, as it is more likely that you already know the tricks but can not see it yet.

        Btw, postponing task until you can solve it means that, you don't read editorial / solutions, and wait until you're more experienced and try again. So you still don't know how to solve the task at that point.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +12 Vote: I do not like it

          I don't believe in any of things like "either you solve it in 30mins — few hours, or you never solve it at all". There are some magic at first glance algorithms like polynomial hashing, interval tree or FFT (which is magic even at tenth glance :P), but there are not many of them and vast majority of algorithms are possible to be invented on our own, for example dp. In high school I used to solve many problems from IMO and PMO and when I didn't solve a problem I tried it once again for some time. And I have solved some problems after third or sth like that attempt. Though, if we are restricting ourselves to beginners, I think that it still holds true, but it would be better to read solutions after some time, because there are so many other things which we can learn, so better not get stuck at one particular problem, when there are hundreds of other important concepts to be learnt.

          → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Try this thing and see if it works for you. After reading the editorial, try to come up with a way of thinking to reach that solution in your own way of thinking. I mean like think about the steps you should make from the begining of your thinking to reaching that solution. In this way you won't only learn the solution for that particular problem, but you'll learn a pattern, a way of thinking and solving problems. :D

        P.S I accidentally hit enter in the middle of typing, so that's the cause of editing. Sorry for that! :D

        → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +4 Vote: I do not like it

    Just read the editorial and try to understand it. You will see that it really gives benefit, because when you can't solve the problem it gives you small piece of benefit. But when you solved the problem or read the analysis you begin to accumulate your experience, understand such kind of problems. It's like learning a foreign language — more you practicing it, the better you understand it.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      i agree with your point about editorial , but i don't agree with this statement "because when you can't solve the problem you are studying nothing, it gives zero benefit" , actually you improve during the process of solving the problem not by solving it , during the process you test a lot of ideas and know which works and which doesn't .

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

Your advices are great,but I would like to add something. First of all you talked about gaps and that we need to solve problems 'out of our comfortable zone'. That is absolutely correct,but I think we must be carefull because in some cases that will be negative because the gap will be so big that even with the editorial we will 'fall down'. Imagine a programmer that can solve just div2 A,and try to solve a div2 E. That would destroy him. Also I would like to add the 'repeatition'. I think is very important to keep the problems in a 'place' that we were stucked and try to solve them again after 1-2 weeks.

→ Reply
»
9 years ago, # |
← Rev. 9   Vote: I like it -38 Vote: I do not like it

This reminds me this (sorry I haven't found an English version) :

Holy God and sinful human

Holy God, Jesus and human

Eek!

http://geoffreyholsclaw.net/wordpress/wp-content/uploads/2011/07/images-2.jpg

https://kdmanestreet.files.wordpress.com/2014/05/bridge-illustration.png?w=300&h=201

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

so now i know for sure your name for GOD is AC!

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

i completely agree with your point , and want to add one more point — leaning from mistakes is very important , if you keep practicing and making the same mistakes every time you will improve but slowly .

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    You're right. Now I'm thinking about how to fit this idea into my gap-jumping framework :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +80 Vote: I do not like it

      Hmm, when you fall, you respawn at the last checkpoint?

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

Wonderful writing . :)

This amazing piece of writing is like a bright light in the dark for us beginners :)

Thank you :)

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

Thanks man for the help. The writing makes a good sense.

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

Thanks a lot I_love_Hoang_Yen. I really try to find something like that The 'science' of training in competitive programming . Thanks again :)

.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Best topic ever

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

Thank you so much, I always ask my friends how to improve my skill in competitive programming and solving problems, but no one answered me like your perfect blog,now think I found the right answer for my question. :)

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

That was v helpful

→ Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it -10 Vote: I do not like it

I recommend binary search on pages to find a page which has challenging problems
And if you know how fuzzy search works, I may recommend that more than binary search
(instead of starting from page 1 and moving forward)

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

After 7 years here a Noob comes to learn the strategy...always remember you

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

yoo

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

I totally understand the logic what you want to explain.

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

Thanks for these important notes , bruh.

→ Reply