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.
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:
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.
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.
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.
Where did I suggest solving a single problem for a month?
Sorry. I couldn't get my message across clearly.
Made the edits
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?
I don't even know how to respond to this. What? Can anybody translate to Human?
Translation: Dont you think its time wasting and not rewarding in the short term to practice on Timus compared to CF?
I wrote a big blog explaining with arguments why is it better to practise on Timus, what answer do you expect?
I totally agree with you
Here is my story. I'm lost in practice in codeforces, atcoder and so on. I mean I only do FAST but not do enough SOLVE. I found that some people around me who have higher rating don't participate in contest too much, they just practice, wirting some blogs, and repeat.
And I want to ask a more question that do you think it' s an effective method to wirte some blogs or notes when someone is learning a new technique.
can only transalte to monke.
monke is hungry, monke needs to eat banana
LOL!
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?
with these muscles, I think that it's easy to find someone
There are plenty of competitive programming communities everywhere around. Just ask question in any of them.
(repeated question)
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
I applied this strategy before having cf account. I don’t see any reason why this strategy is bad for anyone
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.
Same :/
I was forced to agree with the above opinion
Highlight my ass. It's fine.
Does Codeforces problemset feature constitute an archive?
I think by archive he doesn't mean the literal meaning he just means probelmset.
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.
In just 6 days?
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.
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.
And he explained water by water.
And I will repeat this explanation as long as there are people looking for some magical way to learn.
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.
I don't think it's common in many languages/regions, hence the downvotes. Your comment is one of only two with this phrase, in English, that is indexed by Google: https://www.google.com/search?q=%22explained+water+by+water%22&
(I hope I didn't accidentally expose something about your background that you intend to hide lol)
And maybe because your comment can be interpreted as insinuating that Um_nik's advice is useless.
I agree with you.
btw, it's common in China. LOL
why the word part is red
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
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.
.... and learn binary search.
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.
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.
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.
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
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?
That's true.
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.
Gold comment! This is like a reddit LifeProTips kind of advice :)
I can't tell if this is a compliment or an insult.
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.
No, I think topic-wise learning is the worst practice of all.
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.
Yeah you make a good point, I don't think that Um_nik is very familiar with ICPC.
So what is the answer of my question?
I think the first topic you should learn about is sarcasm
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.
why? how should I learn new things and practice them so?
First of all, I don't think you really should. If you know dfs, bfs, prefix sums, binary search, DP and a bit of math (how to do modular arithmetic and a bit of combinatorics) you should be able to get to div1. Adding a couple more things like segment tree, dijkstra and MST should be enough for red. I got red before learning segment tree, but that was many years ago, now you probably need it for red. And for some reason, I think you know much more already.
Second — learn new things organically. When you are stuck on a problem for a long time, ask somebody if you don't know some standard technique. Participate in contests and read editorials afterwards, at least for the next couple of problems compared to what you got accepted. If you see new things — google them and read some articles. Then implement the problem. Several repetitions of that in a natural environment will lead to learning not only the algorithm itself, but also some situations in which to apply it. Yes, it is much slower than solving problems only on that topic for a week, but after that you will be actually able to use the thing you learned instead of just typing it in educational problems when it was given that you have to use it.
Well, I really know everything you have said to reach div 1... I feel ashamed. It seems I have to practice known things, instead of learning too advanced stuff so. Thank you for answer.
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
https://acm.timus.ru/problemset.aspx?space=1&page=all&skipac=False&sort=difficulty
It is true that some problems are more interesting than others, but the general idea of solving archives is to solve all of the problems, even if they are stupid implementations or if you don't like them.
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??
No, I don't think it's a good approach generally.
Um_nik you mentioned to practice fast,contest is important.What are other ways of practicing fast?Virtual participation and lockout matches?
What would you suggest I should do after I see that a completely new thing is being applied to the problem that I am unable to solve. Like say segment trees. Now after learning what seg trees is, should I go back to practicing random questions or try solving some questions related to seg trees so that I know i understood the topic.
What a nice blog! But when I tried to practice as you say, I found that for the problems with the same rating, some I can finish in a short time, but some I have to do for a very long time, such as four or five hours, so how to avoid making training inefficient, or when should I give up trying to solve one problem? Or although I need a very long time, I still have to try till I solve it?
If you are tired or don't feel like you are making any progress, leave the problem for now and return after a month.
A TLDR for the post, summarised by all the colored words: SOLVE FAST CONTEST ability to solve problems problem solving ability level level contest contest fast contests fast solve solve solve contest archive archives contests archives contests
Um_nik I've been at the 1500 level for a couple of years now. I spent the past year or so solving level 2000 problems (Div2 D, since I can almost always solve ABC in contest time). No noticeable progress.
I have to check the editorial ~60-70% of the time for 2000 problems (it's usually one detail that I missed). For 1800-1900 problems I almost never have to check the editorial, so I don't feel like I'm "learning" anything.
What advice would you give to me?
Thank you for the blog post!
Wow i just read the article and never thought these methods in my 10 years programming journey at all. Nice post.
Well... "Not reading editorials util thinking for several months" may be more suitable for kids in school since they have plenty of time. If you start to learn coding just from University and you are now a busy professional, maybe "doing a lot of problems and read editorials when you get stuck" probably is better... Don't know, since I'm weak TAT
Since I'm Newbie right now, I'm gonna follow this tips for 1 month, soon I'll share the experience I'll try to read atleast 10 problems a day of div 2 (A & B & c) and try to solve the problems without seeing the editorial
So that means you won't try to go back to problems you don't solve now, after a month?
DELETED
Anyways, after looking at the problem, you'll most surely guess the topic
OP has answered this above.
Thanks, dude!
Um_nik Is it a good idea to look at the failing test cases if you are not able to find why code is failing ? Great Blog BTW .
You probably mean to look up the test in the testing system? In this case, the answer is no. You won't be able to do that in contest, so you need to learn how to debug without that. But you can find the test on which your program is failing using stress-testing (running on a lot of small random cases against a slow correct solution).
Thanks .
Is the Atcoder Beginner Contest a good enough archive?
Um_nik is Googling okay? I get that you should not look at editorial and you should not see test cases. I agree with that. However, do you think Googling is okay? An example would be if I forgot about how to implement a specific algorithm, checking insertion time of some data structures, searching for prewritten code for like finding factors of a number (sometimes I mess up the details when writing myself), etc. On the one hand, I feel that I should not rely too much on Google. On the other hand I feel like that might not spoil the practice too much. Any ideas? Like I think for factors of a number or for example recursively generating all subsets, I should think through it myself and not Google.
If you really understand the algorithm and have made enough practice for it,i don't think you can forget about it that easily.Why? because it becomes a muscle memory.I have never used BFS for a long time yet i can still write it no problem.I think the only issue for you is that you are using too much prewritten code.I suggest you to redo all algorithms that you have learnt and rewrite it using your own style,therefore it'll become a habit.If you are stuck,google ONLY ONCE.Make sure you really understand what you are going to write.
"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."
Um_nik, can you please explain this in detail? Among the 10-15 problems, how to choose 1 problem that I want to solve? Because I only know what statement says in these problems, but I don't know how these can be solved. So how can I choose problem order from 10-15 problems, that I opened? or should I think about multiple problems parallelly?
The one you liked best
Thanks for this blog Um_nik !... I am happily crying!!!
Your kindness is greatly appreciated.
This is such a great post, this:
I thought I'm doing something wrong and hence facing the above challenge, now I know. The point on contest and archive is really great. I'll follow this religiously and see where I'll end up.
This is a note to myself, I'll work hard and get better