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.
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.
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.
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, ...
The analogy with gaps makes sense. I wouldn't call it "science", though — it's just a way to view "practice makes perfect".
Thanks, but I can't come up with better naming :(
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.
there is no such thing as being "smart" or being an "idiot" all people have a thing their good at.
I think "Practice" is American while "Practise" is British. Just like color and colour.
I was unable to refrain from posting that.
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
It's grammar nazi, actually. Or, if you prefer
well it wasn't grammar so i said "vocabulary"
"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.
It would be great if you take out time to explain that math too .
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)
The better term is ACTIVATION ENERGY , mate
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.
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).
What to do if there is no proper idea for the task?
As written in my last sentence: look at editorial, ask for solutions.
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
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.
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.
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
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.
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 .
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.
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
so now i know for sure your name for GOD is AC!
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 .
You're right. Now I'm thinking about how to fit this idea into my gap-jumping framework :)
Hmm, when you fall, you respawn at the last checkpoint?
Wonderful writing . :)
This amazing piece of writing is like a bright light in the dark for us beginners :)
Thank you :)
Thanks man for the help. The writing makes a good sense.
Thanks a lot I_love_Hoang_Yen. I really try to find something like that The 'science' of training in competitive programming . Thanks again :)
.
Best topic ever
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. :)
That was v helpful
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)
After 7 years here a Noob comes to learn the strategy...always remember you
yoo
I totally understand the logic what you want to explain.
Thanks for these important notes , bruh.