I understand that CP can't be described in few notes but I really want to hear from stronger competitive programmers some short ideas, rules and tips that help you while solving and/or coding difficult problems. I'm not talking about training in general but some tips on how to approach or what not to forget while solving and/or coding. Might be generic or specific. Anything. Many thanks.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 11:21:59 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
this is so purple
This is so orange
Then this is so blue :P
That is so out of loop
I know that by such things people may mean magic pills or universal algorithms that solve all problems but I look for something real like what first do you think when seeing probabilities, where should we be careful in, say, CHT implementation or what are your first steps while constructing greedy, etc. I kinda want to make a list of suggestions and share it with CP amateurs like me.
Questions like "what first do you think when seeing probabilities" are useless before you solve enough of probability problems and meaningless after. Same for everything else you've mentioned. Just solve, upsolve and read editorials, don't look for easy ways.
** Cyan says some short ideas
** MetB : would it help ?
:'D
(TL;DR at the end if you're lazy)
It is well-known that, in order to master something, you have to be able to teach it. I think it applies to solved problems too.
When you solve an hard, interesting, many-steps problem (not a random cancer CF problem), try to write a complete document about it (few pages), where you will explain all the thinking process that leads to the solution.
IOI-style problems may be good candidates for that, because the subtasks format will naturally divide your solution into several thinking steps.
Everything should be clear in this document, and the path leading to the solution has to be natural (unlike most editorials which don't explain how to come up with the solution). You may have to make your solution as simple (and elegant) as possible before writing.
While explaining the solution to the specific problem, don't forget that the document also has to give general problemsolving adivces (related to the problem, of course) :
When you use some sort of technique/trick/observations, try to write an aside about it (why we should think about it in this case, in what other cases is it useful, try to find corollaries and generalisations).
When you're doing greedy things, don't write a formal and obscure proof, instead write an intuitive justification (it may be harder to find).
When there is a potential wrong solution that looks attractive, explain why it's false, and how we can find a simple counterexample (e.g. testing resistance to "noise")
etc...
In the last part of this document, summarize all useful tricks or "method points" you learned while solving this problem.
This "teaching part" is in my opinion the only way to really fix in your brain all the nice things the problem made you discover. Unless you did it, I don't think you can consider that you completly solved the problem.
TL;DR Solve hard and interesting problem, and write a complete document explaining a natural thinking path that leads to the solution (how to come up with it), with asides about techniques or method points used.
Good point. Many thanks.
That's a lot of time spent on one problem. Doesn't sound efficient to me.
Well, it's quality over quantity. I tested both, and spending more time on fewer and harder problems personally gave me better results. But it may not suit everyone, there is no universal practice method anyway.
Actually, if we're solving hard enough problems, writing this document will not be longer than actually solving the problem, so it's at much twice as slow. That means that we will solve 2 times less problems, but they will have a way bigger impact (at least for me), so I think it's worth it.
That's of course two different spirits of training. The quantity helps in fastsolving and gathering a lot of classical knoweldge quickly, the quality helps to improve thinking ability and extend "comfort zone".
Both things are important in div1, so one should probably mix these two type of trainings.
How did you test and compare the two methods?
For the first method, I was doing during few months a lot of problems that I would solve in like 30-60min (max 90min), mostly on Codeforces, easy OI problems too. I upsolved problems that I could have solve in contest with more time, and read editorials for others.
I learned some classical tools (suffix array, HLD, Dinic, ...), it was nice. But now that I know all classical tools, and MetB probably do too, it's not an advantage anymore.
I was faster on problems I was already able to solve during contest. Being "quite fast" instead of "slow" is nice. But once I was "quite fast", being "very fast" on easy problems didn't matter much, except in Speedforces (as some "quite fast" people would solve harder problems and beat me anyway).
I still couldn't solve problems outside my comfort zone (D1C was too hard). If I continued this way, I think I would have reached a peak like MetB.
Outside focus of this blog, but it was almost totally useless for OI. Almost no progress here.
For the second method, I looked at harder and more interesting problems (rating+300 on Codeforces, JOI Spring Camp, ICPC World Finals, ...). I usually spent 3 to 5 hours on these problems (eventually asking for hints, avoiding editorial, trying to get my own intuition of the problem). Writing a document was like 1h30.
I was really happy to solve these problems, made me feel that I really made an important acheivement (and motivation is very important when practicing and trying to outcome a peak).
It forced me to totally change my mindset and my approach of problems (developing a new problemsolving method, more rigourous), while the first method only consolidated my current approach which was quite bad (bad habits like not verifying solution before coding it, trying to guess the solution without using paper, thinking directly of the whole problem instead of thinking about simplifications, ...)
It made me really remember important "lessons" and think of other cases it would be useful, thanks to teaching part. Thanks to that, I'm in a sense able to "connect problems together".
It made me reach next level of problem difficulties (D1C), even if I'm usually quite slow to solve them.
Now that I wrote this, I realized how the two methods could eventually be combined:
Use second method (solving hard problems) to exit the comfort zone, outcome the peak and reach next level.
Once this next level is reached (usually being able to solve them in contest), use the first method to consolidate the comfort zone (always being able to solve them, and quickly enough).
Once the new level is mastered, repeat the process.
Writing a document was like 1h30 ... can you share some of these documents with us ? i'm interested in your in your method and i want to see some examples of the explanations. thanks in advance.
I write them in my native language (french) unfortunately, as my english skills are quite bad. You can still see the one I made for Pizza Delivery if you want (complete, even if it's not a problem I totally solved myself): https://www.docdroid.net/evOOt8P/pizza-v2.pdf. For some problems I did handwritten notes instead of LaTeX document.
And by the way, I'm not sure that this method is actually suited to participants below purple, because I don't really know many-steps problems suited to you and enough interesting to write a document about. Well, I didn't test it when I was cyan, so I don't really know.
You just explained that it's good to solve hard problems (outside your comfort zone).
Yes, and spending a lot of time on them, answering your first comment. Writing takes only a supplementary hour on these problems solved in 3-5 hours, so it's not a loss of time (in fact, I never felt so efficient), helps taking a global view on the problem and extending the interest of the problem to more general cases. I now perfectly remember the problems I wrote something about (and their solution), and forgot almost all other ones.
I'm just saying that you don't have a comparison between "solving hard problems" and "solving hard problems and writing solutions down".
I'm sure that I gain something more when testing problems, discussing them, spending a lot of time, albo setting contests and writing editorials. But I think that just solving hard problems is more efficient, that's it.
Do consider writing editorials (or blogs). You will get paid (well, that depends on the platform) and the community will get something valuable. A win-win.
Your comments are much better than an average editorial, don't worry about it. But I understand that it could take more time then.
Oh, sorry for the misunderstanding.
I do get that writing solutions down may not be efficient for everyone. As long as one has a clear solution and doesn't forget about the problem as well as the things they learned solving it, it's fine. Writing a document assures you that this goal is reached, but it might not be worth taking the time to do so for those who have an organized mind then (unlike mine). Thank you for your feedback!
I didn't know about that, thanks. I'm currently busy with problemsetting, but I'll probably try it in the future.
Hi could you please upload the articles you write on your github for people who understand french ? It's often hard to find clear explanations for OI problems.
By "D1C", are you referring to Division 1 C Problems?
You forgot the most important step: Post it for contribution.
I endorse this approach, and this is what I've been actually doing for a long time. I have a Korean blog where I started writing for about 5 years, spanning my whole CP career (my article from 2014 is about finding shortest paths, and maximum subarray algorithm).
It really takes a lot of time, because I usually use about 2~10 days for writing a single article. While I'm still struggling to make it faster than now, I believe writing makes a better person, which is important than being a better competitive programmer.
Btw, I always think about making English blogs, but it's quite hard for me for various reasons (not including language barrier). I'm really trying to deliver something in early August or September, stay tuned :)
try to approach the problem by your own.
Well I have a question in which I hope other's can give me advice on.
When upsolving, is it very important that one always implements the solution, or sometimes should I just "theory solve" the qn, and skip the implementation to instead focus on having more exposure on other questions? Thank you!! :)
I would suggest implementing it as the way to practice coding skills and just spend time with the problem to remember the solution well.
If you are a beginner -> just implement everything.
If you are experienced -> If the implementation is simple or you were like a simple observation or 2 away from solving the problem then skip otherwise implement it.
Well, as one wise man once said, just solve more problems.
One CM to another CM: Never ask Red coders...
Yeah man. Never ask a red coder. Have some self respect and pm a nutella.
I think the most important thing I learnt is that it's always optimal to think carefully and understand a solution completely (maybe on paper) before implementing it.
First of all, in team contests it obviously saves computer time. If you have 15 hours of human time and 5 hours of computer time, it's usually better to optimize computer time which can be spent on implementing and debugging and so on. It's dangerous when the guy who took the computer tries to finish his solution and the computer is not actually involved.
Moreover, I noticed that when I participate in an individual contest, it's still better to think of all details of a solution before starting it. I don't always manage to take everything into account, but the strategy "I start it now, write everything that is definitely needed and then just deal with the rest somehow" usually leads to nothing good, no matter how tempting it seems. I noticed that with the right strategy I have to debug much less my solutions than earlier.