Archive of my solutions to various problems in competitive programming. If it is not obvious how a certain solution works, there may be some in-code comments detailing the steps taken (not guaranteed!). If you are confused about anything or want me to write an editorial for a problem explaining how to do it, feel free to send a message (chroniclesofcode on codeforces, or just make a pull-request...)
Note: I have also included questions from leetcode, which is not exactly competitve programming but still 'algorithmic'.
- Do not force a particular algorithm/methodology on a question. A lot of people come in with a mindset of 'is this DP? greedy? queue? dfs?' which is bad. You should be flexible and it's very common that a question will try to trick you into thinking it is a certain archetype.
- Try to make 'observations' that chain onto each other. Things that lead onto things will give you very logical conclusions and you can finally apply a generic algorithm at the end. First, turn the problem into something very simple - then you can finally ask 'is this DP?'.
- Upsolve. Solve questions above your level, that challenge you. This is well-known but most people need a reminder: life begins at the end of your comfort zone. If it doesn't challenge you, it doesn't change you.
- Another note about upsolving. If there is a contest problem you cannot do, solve it - then solve more questions of a similar style. It is easy to just solve it and move on, but that doesn't test if you truly learnt it.
- Spend less time trying to pick the 'optimal' questions. Just solve and solve - the more problems you do, the more experience you will gain. It doesn't matter what website, what judge - as long as it improves your problem solving skills it is valuable.
- Try hard on a question. Don't give up so easily - if you read an editorial, you should be able to definitively say what is something you will do differently next time when faced with a similar problem. Too many people give up too early, and end up just implementing the editorial. We are not solving these questions to improve our implementation skills, we are solving them to improve our problem solving skills.
- Stop learning algorithms (most likely). A large amount of competitive programmers (even up to a fairly high level) spend a lot of time learning algorithms - this does not improve problem solving, and essentially wastes your time if the question doesn't appear in the contest. Only decide to learn an algorithm when you are at a level where you judge it a necessity to perform - most likely, this level is much higher than you think. Of course, if you find learning algorithms really fun like me, and if you aren't too concerned on the 'fastest speed of improvement', then go for it!
- Never get stuck on one approach. If you watch top competitive programmers (e.g. tourist), you will notice he will try many different ways to tackle the problem quickly, and never gets stuck on one methodology. This goes back to the first entry "is this greedy?". People will always try to force what they think is right on a question, and the deeper you go, the less you want to restart from scratch. Your mind is lying to you - it is really no big deal to abandon your current approach if you aren't at the solution (even if you are 'very close to the answer'). Tourist has once said as a kid (gold medalist-kid however...) "I try various [strategies], and one of them is the right one. I am no genius. I am simply good at it."
- If a problem is hard, don't be afraid to get your hands dirty! Make some test cases, maybe n=6,7 and really wrestle with it. Apply your algorithm on it - what do you see? For beginners, they see a lot of high-level programmers neglect this step and think they should neglect it as well. Don't. Only neglect it if the question is truly too easy for you.
- What is it about this problem that is difficult? What aspect? What does it change? What can I do to make this problem easier? What would be the solution without this constraint?
- Try hard (again). You don't improve when are solving questions. You improve when your brain is backed up against a wall, and all your possible (failed) solutions have been exhausted. It is trapped, and has to come up with new ideas to escape. This is when your brain grows the most, and is the most creative. It is the same with muscle growth - 80% of all growth comes in the last 20% of your set. It is those last reps that actually count. Now do the same with your most important muscle - your brain.
The above advice is generally regarded as 'good' advice and taken from all sorts of sources. However, this section is mainly going to be my personal 'theories' on perhaps how to improve at competitive programming at an even better rate. I'm not a top-level competitive programmer, so take my advice with a grain of salt, but perhaps one day I will be reputable enough that this advice should be considered seriously.
- I believe that 'intuition' for problems comes from the culmination of your knowledge bank of all questions that you have done before. However, it is very easy to forget a solution to a question you did months or years ago. Therefore I believe that a repo such as this one is vital to quick improvement in competitive programming. Every so often (maybe once a week), one should read through certain questions and attempt to come up with a solution relatively quickly in their head. If they are unable to do that, then they will revise and 'memorise' the solution that they had already written. So basically, you are testing yourself to see if you still remember the content. If the question is ridiculously easy, remove it from your solution bank. Otherwise, keep going until you are able to confidently answer 99% of all questions in your solution bank within the span of a few minutes. Then you can be confident that the questions you do from now on are built upon a powerful foundation of hundreds, thousands of questions that you had not forgotten.
- Currently, I am using Anki with a collection of all the problems I have solved to test my hypothesis. Since it has a much faster turnover rate, we are able to study our flashcards every day, testing ourselves on the problems we have solved before.