Um_nik's blog

By Um_nik, history, 12 days ago, In English

CP is about solving problems fast. And as absurd as it may sound, I believe that SOLVE and FAST are very different and almost independent parts, and you need to practice them separately.

Let’s look at some contest, like a CodeForces round. For the sake of simplicity let’s assume that every problem has some difficulty, which is a numerical value denoting how hard it is, bigger values correspond to harder problems (it is not true, but it is an ok-ish approximation, at least if we consider subjective difficulty for a fixed person). Contests are made for a wide range of participants, and problemsetters strive to make contests interesting for a wide range of participants, which means having a smooth difficulty gradient. Well... as smooth as it is possible with 5-6 problems.

Graph 1

On the moment of a contest you have some ability to solve problems. If we assign each problem with numeric difficulty, it is reasonable to say that your problem solving ability is also a number on the same scale. But it doesn’t mean that you can solve all the problems below your level and can’t solve anything above your level... it’s more like “probability distribution”, or maybe how much time you need to solve the problem of given difficulty:

Graph 2

The issue is this probability distribution is something close to sigmoid: You can surely solve the problems that are much lower than your level and you solve them almost instantly after reading; on the other hand, you need too much time, maybe even infinite time, to solve problems way above your level. And that interval of difficulties which is not too easy while not too hard for you is rather small. Let’s call this interval interesting.

Since one contest has only a few problems and should cover a wide range of difficulties, there is usually one problem in your interesting interval, rarely there are two, sometimes there are none. These are the situations to which some participants refer to as speedforces: your result in the contest depends on how fast you solve easy problems. I don’t want to disappoint you, but almost every contest is a speedforces contest in a sense that your result is mostly determined by your speed and accuracy on easy for you problems or, how I call them, problems that you already know how to solve. In a contest, you don’t have time to come up with something completely new and original. Yes, you need to get what is the problem about, unravel some layers of reductions and implement the solution, but in a nutshell you know how to do every small part of the problems you will solve in the contest before the contest even starts.

What I’m trying to convey is that in a contest your goal is to solve the problem that you already know how to solve fast. By doing X you learn how to do X, so by participating in contests you learn how to solve problems fast. But then where do you learn how to solve problems?

To learn how to solve problems you need to solve problems, solve problems that you don’t yet know how to solve, but that are possible for you to come up with, maybe using a lot of time. These are the problems from the interesting interval, slightly above (or below in some cases) your current level, but not too much above because otherwise you can’t solve them yet. So we need to somehow find a lot of problems near your level, how to do that? The answer is rather simple: go to a place that has a lot of problems of various difficulties and doesn’t have a time limit. It is not a contest, it is an archive.

Graph 3

Just by having a lot of problems archives can almost always provide a problem of needed difficulty. And you don’t really need to do anything special to achieve that: sort the problems in the archive by difficulty and solve them. After the first period when the problems are too easy for you you will always be at a level where the next problems are the right difficulty for you because after solving a hundred problems your level will rise a bit, but so will the difficulty of the next problems.

I notice that nowadays many people start from CodeForces contests, and I think it is bad and it is the underlying reason for many frustrations. Some things that come to my mind:

  • Newbies are ok with repeating problems in contests, problemsetters shouldn’t be so worried about problems being fresh — you should solve old problems in archives, learn classic techniques there and then use them in contests, contest problems need to be fresh.
  • Where will we learn stuff if in contests there are no problems on classical techniques — again, learn the techniques themselves in archives, then you will see that there actually are problems that use classical techniques in contests, and obviously, there should be no problems that just are classical in contests.
  • It is hard to make a training regime out of contests — it is, and you shouldn’t do this, contests should be only a part of training regime.
  • Contests allow that self-deception thing: you can solve a lot of problems in contests, but they are the problems you already know how to solve and that doesn’t increase your level.

The questions that I anticipate (ask your questions in the comments if needed):

Q: How long do I try to solve the problem in the archive before reading the editorial? Like, 30 minutes?
A: You don’t read the editorial. The best option is to choose an archive that doesn’t have editorials at all, so you don’t have to fight the urge to look at the solution.

Q: Ugh, and what should I do if I can’t solve the problem?
A: Abandon it, for now, switch to a different problem, return to it after a month or so. My usual approach was to open 10-15 problems, read them carefully, think a bit, choose the one I want to try and solve now, try for some time. If I don’t feel like I’m getting anywhere, switch to another problem.

Q: Month?!
A: Maybe even more. You need time to acquire new skills and discover new ways to look at this problem (by solving other problems). It doesn’t make sense to return in less than a month because you will only run through the same ideas you did before.

Q: Ok, but how do I learn new techniques if I don’t read editorials? I’m not supposed to invent everything on my own, am I?
A: Most of the time you don’t need to learn any advanced stuff to solve the problem, you can’t solve it because you are not trying hard enough or not paying attention to details or just being stupid. My experience even says that most Russian schoolchildren who do CP know too many algorithms.

Q: But there are problems that require some standard things!
A: OK, yes. The best option, in my opinion, is to have some person around who solves the same archive and is better than you. In case you are stuck on a problem for a long time (that’s not an hour, that’s several months) you should ask them “Do I have to know some standard technique to solve this?” Pay attention: not ask how to solve, or for a hint, just a yes/no question. Most of the time the answer will be “No”. In the case of a positive answer, they will be able to send you a link to an article or what to google to learn about the technique. After that, you still will have to apply this technique to the problem, and you are more likely to actually remember how to use it and why did you need it in the first place, which tremendously increases your chances to use it successfully in the future.

Q: OK, which archive should I use?
A: It is not that important, but you should use one and stick to it. I have used Timus because I’m from Ural region, there are numerous others: UVa, SPOJ, Codeforces archive (has editorials and too many problems, thus a warning) etc.

To sum it up:

In archives you learn how to solve problems, in contests you learn how to do it fast. I’m not saying that contests are not needed: speed is also very important, and it is good to keep you in competitive shape. Also participating in contests is just fun, that’s also very important.

Acknowledging this and separating learning how to solve from contests can lead to better training, I believe.

How to split the time between archives and contests? Well, contests are held in some fixed time, so when there is a contest that fits into your schedule, you shouldn’t miss it. Turn to archive when you want to practice and solve something which should be often, otherwise CP is probably not for you.

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

»
12 days ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

Partially agree with you.

I agree that seeing editorials after 30 minutes is kind of stupid. There are problems that will take more time and some that you know straightaway that you wouldn't be able to solve.

However the point about solving a single problem in various different months is something I wouldn't suggest to a newbie(or even a pupil or specialist for that matter). The reason being that easy problems are easy for a reason . Dragging them out will achieve nothing except wastage of time/brainpower and probably self deception.

The point about algorithms I completely agree with. I am yet to understand the weird love of dynamic programming in India. If anyone can provide a reason for this obsession , I would be highly obliged.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Where did I suggest solving a single problem for a month?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Sorry. I couldn't get my message across clearly.

      Made the edits

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't u think that solving problems from Timus takes much more time than doing the same thing on Codeforces and it is not that rewarding in the short term?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    I don't even know how to respond to this. What? Can anybody translate to Human?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Translation: Dont you think its time wasting and not rewarding in the short term to practice on Timus compared to CF?

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

        I wrote a big blog explaining with arguments why is it better to practise on Timus, what answer do you expect?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      can only transalte to monke.

      monke is hungry, monke needs to eat banana

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it -29 Vote: I do not like it

      Translating it using Google: Result Not Found! , Google doesn't support these alien words!!

»
12 days ago, # |
  Vote: I like it +14 Vote: I do not like it

What would your advice be for someone who doesn't have a person around to tell them whether some new standard technique is required or not?

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +64 Vote: I do not like it

    with these muscles, I think that it's easy to find someone

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    There are plenty of competitive programming communities everywhere around. Just ask question in any of them.

»
12 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

(repeated question)

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

I think it's a very good strategy for above-average-rated people like >=CM or something, but not beginners, especially those who lack mathematical or programming background.

P.S: This if ofc just my opinion and it would be interesting to see the newbies I'm used to seeing follow this strategy and see if it's more effective than normal "Solve random problem rated + 200 or so" strategy

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    I applied this strategy before having cf account. I don’t see any reason why this strategy is bad for anyone

  • »
    »
    25 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep i agree too and feel this technique is going to have cold start to us newbies and pupils and one will probably feel it easier as he goes practices on a expert and CM level, beacuse like it says, u need to know the problem before hand to solve it in a contest. The learning therefore has to be during the practise times and solving the questions by yourselves is the best way,then the skill of idea-storming is enhanced.

»
12 days ago, # |
  Vote: I like it -8 Vote: I do not like it

I have a situation. I want to solve a lot of problems on dynamical programming, but all the problems are rather too easy (can be solved in 15-30 minutes) or too hard (can’t invent an algorithm at all, even after several monts). What do I do?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, there are lots of DP problems on timus. Maybe you will find some interesting DP problems there

»
12 days ago, # |
  Vote: I like it -7 Vote: I do not like it

This also should be added to Catalog section. That too a very 1st article

»
12 days ago, # |
  Vote: I like it +47 Vote: I do not like it

The text is somewhat difficult to read due to the presence of colored words((

It seems to me that it would be worthwhile to additionally highlight them in bold for easier reading.

»
12 days ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

Does Codeforces problemset feature constitute an archive?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I think by archive he doesn't mean the literal meaning he just means probelmset.

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Excellent concept! Using archives to learn how to solve problems, and learn how to solve fast by participating contests. It helps me a lot, thanks.

»
11 days ago, # |
Rev. 2   Vote: I like it +79 Vote: I do not like it

I agree almost completely with this. One point that is obvious to me but it seems people don't get is that speed can also influence your solving ability (maybe a better word is potential?) during contests in the sense of in a contest with limited time you have limited time (duh) and solving doable problems faster leads to having a higher margin to try some problem above your capacity.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Add Kattis to the list of OJs. Kattis has difficulty ratings (unlike Uva and SPOJ), no editorials and good collection of old regional ICPC/IOI contests.

»
11 days ago, # |
  Vote: I like it -19 Vote: I do not like it

To learn how to solve problems you need to solve problems

And he explained water by water.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    And I will repeat this explanation as long as there are people looking for some magical way to learn.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You didn't get the joke LOL

      I'm not saying that what I quoted is wrong. It's just a common joke when someone try to explain something obvious and ending up explaining it by itself.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    This is also the best way to properly learn recursion.

    spoiler
»
11 days ago, # |
  Vote: I like it -25 Vote: I do not like it

why the word part is red

»
10 days ago, # |
  Vote: I like it -6 Vote: I do not like it

It would be very helpful if u can give a difficulty range for timus like what a CF 1700 rated problem is on timus will be ,i searched for that but didn't find anything realting

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Find comfortable range of difficulty yourself. I just want to mention that some of difficulties listed on timus are definitely wrong just because they are linked from some other sites like here as good problems for practice, so people go there and solve it more frequently than other hard problems making rating for the problem lower than what it actually would be without advertising.

»
10 days ago, # |
  Vote: I like it +20 Vote: I do not like it

.... and learn binary search.

»
10 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Nice way to practice. I have read that you like timus a lot, always thought maybe you’re just good enough to actually like it even when editorials are not available. Makes sense now, I like this way. Will go through this method if I sometime decide to try competitive again sometime.

»
8 days ago, # |
  Vote: I like it +16 Vote: I do not like it

I want to add that not only looking editorials make bad influence, but also looking tests. Because you have same urge to look test which fails your solution. I remember I got downvoted when I said that in EDU section tests should be hidden.

Availability of editorials are nice in perspective that you can always verify yourself that problem and solution are correct. Sometimes editorials are bad though. Bad side is for people who can't hold themselves to look there instantly. And instant published editorials makes this situation a bit worse for those people.

BTW I know one person with 2400+ rating who look editorial straight after virtual contest is over.

»
6 days ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

Benq said sometimes he reads the editorial for a problem before he even reads the problem (see here)--I'm curious how you reconcile that with your approach. (Also I'm not sure for what % "sometimes" means and for what problem difficulties he does this.)

Although I still err on the side of spending more time on solving a problem, intuitively it's hard for me to believe that someone who solves 1,000 problems because they look at editorials will be worse than someone who spends a long time per problem and solves 100 problems. The main (indirect) counterargument I see is that you could say for top performers, they have all solved around the same number of problems so at the top it only matters the "quality" of problem solving you do. It would be very interesting to run well-controlled study on this.

IIRC I read a study on teaching math (maybe CS?) that argued that giving students guidance was much more effective than letting them struggle on their own, but I can't find it.

  • »
    »
    6 days ago, # ^ |
    Rev. 2   Vote: I like it +65 Vote: I do not like it

    just to be clear, that is definitely not a good strategy and I don't do that on a regular basis, I should remove that from the guide

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

      I don't think anyone thought you condoned that strategy, but (at least to me) it conveyed that you didn't shy away from editorials. Is that not true, or do you usually take an approach more similar to umniks?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    Using advice from top competitor on HOW THEY TRAIN is a really bad idea, unless you are already a really good competitor and have a good understanding what works for you and what doesn't.

    This holds for other things in live. If you started training like Mr. Olympia or World Strongest Man because you saw a video on how they're training, then you will most likely injure yourself. If you decide to ditch sleeping normally and start sleeping 2 hours 4 times a day, because you saw an article claiming that CR7 does so, then you will most likely become constantly tired and develop serious mental problems.

»
5 days ago, # |
  Vote: I like it -26 Vote: I do not like it

Is it true that you read a topic from a book and then solve the exercises and the problems related to this topic? (Like in competitive programming 4 book)

Thanks.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    No, I think topic-wise learning is the worst practice of all.

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      Even for ICPC?

      In ICPC the problem set consisting of about 10 -> 13 problem and each one from different TOPIC.

      so I actually don't know if I should practice for ICPC or for CODEFORCES contests.

      Thank you.

      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it +153 Vote: I do not like it

        Yeah you make a good point, I don't think that Um_nik is very familiar with ICPC.

        • »
          »
          »
          »
          »
          3 days ago, # ^ |
            Vote: I like it -41 Vote: I do not like it

          So what is the answer of my question?

          • »
            »
            »
            »
            »
            »
            25 hours ago, # ^ |
              Vote: I like it +7 Vote: I do not like it

            I think the first topic you should learn about is sarcasm

          • »
            »
            »
            »
            »
            »
            23 hours ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            In all seriousness, during ICPC contests you will also find that there are 1-2 key problems that will determine the position around your level. Of course, you also need to be fast on easier ones, but you'll generally get that with experience. What matters most is the ability to gradually be able to solve harder problems of various kinds as your training progresses, which is what the proposed way of training is designed to achieve.

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for sharing this. Since you mentioned about archives from an online judge (Timus for instance), how do you find the "interesting" problems out of lots of problems on the archives? (Because we might end up in some kind of time-waster implementation problem that does not quite "add" our solve factor)

Or do you perhaps have a playlist you'd like to share for "good" problems in Timus? Thanks

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Sir, I want to ask as you and some other great cpers mentioned that you must not check editorial until you fight and try everything you could ( or completely not checking it), I want to ask to get a taste of problems that are way too difficult and requires really new techniques( new to us), Can we just understand problem and its solution? Will that help as its not obviously in our range of solvability but getting new approach ideas will help to solve problems of my range?? Like I am a pupil, should I do this for problems above 2000??

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, I don't think it's a good approach generally.

»
4 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

Um_nik you mentioned to practice fast,contest is important.What are other ways of practicing fast?Virtual participation and lockout matches?

»
29 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

I like this idea of coming back to an unsolved and tried problem. I decided to come back after a week to the same unsolved problem(In this week, I will try to think a lot). Comeback -> Try -> Can't Solve -> Read Editorial and keep the idea in the brain and store it somewhere -> Return after a month and revise the ideas that you could not get in the previous month and again solve them. It now becomes a cyclic graph until u master it. Usually people forgets after a month (So a month :)) you may vary the period.

This helps!