6

How to Effectively Practice CP + Problem Solving Guide

 1 year ago
source link: https://codeforces.com/blog/entry/116371
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

This is a slight tweak of a practice guide I wrote a while ago on USACO reddit since I thought it could be helpful to people here. Some USACO specific sections or extra clutter I left out here that aren't needed for a general audience.

Introduction

This is a post on how I believe is the best method to practice modern day competitive programming based on my experiences. I assume you already have some knowledge and know simple things like binary search and dfs/bfs, but read the footnote if you are complete beginner.

First, a quick tl;dr of the practice strategy before a bunch of specifics and explanation:

In short, mostly you only need to use codeforces (no matter what contest you're training for), find a rating range where you can solve around ~30-40% of the time on your own, and just grind down the problem set tab in reverse order of id (the default sorting). Also take part in every live contest you can, and virtual any live contests you miss.

Also, if your primary goal is some goal outside of codeforces (let's say USACO, but could replace with any OI or if ICPC replace instance of OI with ICPC) Approximately once per week (probably on each weekend), I recommend you virtual an OI contest then upsolve the ones you understand the editorial for after. This should be old usaco contests until you finish all in the past 5 or so years, then use OI checklist to find new contests. Make sure you go for subtasks just as you would in real contests when doing so.

Some parts of this method may seem strange to you, so I'll explain in more detail and comment on why I believe it is the best method, and give some proof. If you're too lazy to read all of it, the most important parts of this article are bolded. Also, I am assuming you are able to practice somewhat regularly (at least a few days of practice done each week for multiple months), and this practice is unlikely to work if you don't. However if you really want to improve fast, ideally practice should be daily, no breaks.

Goal of Practice

First off, what is the main goal in practicing efficiently? I would argue you want to come across as many subtle ideas and concepts as quickly as possible and learn to intuitively realize when to apply them. This is what my practice method is centered around.

Another important goal is you should also feel discomfort in effort of trying to think new ideas as much as possible, but don't mistake this as time being confused with discomfort having no idea what to do. Actively making new insights as fast as possible is the state you should be in a lot during live contests and need to endure actively thinking new ideas while trying to not repeat same ideas in your mind. But when you have no clue how to approach/understand a solution to a problem, you are more likely to lose focus and are not helping yourself.

Why Codeforces?

So, why only codeforces? Well, recent codeforces problems do a decently good job of introducing a large variety of concepts, particularly in the 2000+ rating range. Thanks to the large standards of wanting non-standard problems each contests, many small math tricks and greedy techniques are introduced, along with standard algorithms and data structure appearing decently enough. This is why I think they are the best collection of problems, as opposed to many other judges that are more standard and less diverse or innovative. Recent codeforces contests are by far better than old contests however, so that is why you should grind down the problems from most to least recent in the problem set tab. If you have done all contests later than contest 450, you should probably start using another judge and start doing more virtual contests, but at that point you probably don't need this guide.

How to Approach Problems in Practice

Alright, so codeforces seems good. Why only a rating range where you can solve ~30-40% of the time? Shouldn't you be practicing coming up with solutions on your own? Well, like I said earlier, you want to come across as many concepts as quickly as possible. If you're able to solve ~80%+ of the problems you're doing on your own, even if it takes a while, or in fact especially if it takes a while, you are not using your time most effectively, as you were already able to come up with the concept on your own. It is OK to read editorials often, that is where you actually learn new things. Binary search on the problem set tab to find a rating range of problems that fits the ~30-40% specification, and I recommend the rating range to a few hundred points wide.

Well, the next natural question is how long should you take before reading editorials? I will argue only spend 15m thinking, after that if you're still having ideas keep thinking, but if you're just stuck read the editorial. However, if reading the editorial gives you new ideas continue thinking again. Sure, you may discover a trick you came up with yourself you can use later after a long time thinking, but was it worth spending 3h coming up with the solution on your own when you could've gone through 2 or 3 more problems if you read the editorial instead. However, going through too hard problems is just as bad is going through too easy problems. It is not worth spending 4h understanding a 3000 rated problem when you could learn much more concepts from 4 2300 rated problems in the same amount of time (if that's good for your skill level). That's why I say ~30-40%, this is usually the point where you can understand the editorial relatively quickly but aren't able to see the concepts on your own. Also, this is another reason to use codeforces instead of other sources, the problems are shorter so you can get through more faster and it is easier to find many problems of similar skill level.

Some important notes, however, are to take the 15m of thinking very seriously and implement every problem. This is extremely important!!! you should only be looking at editorial when you are really out of ideas and trying to think longer will just make you unfocused or reiterate old ideas. It is important to practice making observations on your own, and you should be solving problems in the range more and more often as you go down the problem list, that's how you know you're improving. You may think you can get through more concepts earlier without implement too, and this would fit the main goal of practice better, however, it's important to always implement every problem that isn't completely trivial, even if you mind solve it on your own, as you will remember it better and often you will realize you didn't understand the details as well as you thought before implementing.

I also recommend timing yourself when doing problems, at least while implementing. This will help you stay focused and improve your implement speed (which is important so you don't waste time implementing in contest). If you record your times you should hopefully see yourself getting faster for a fixed problem difficulty :).

Also, it can be good to look at others solutions after you finish a problem quickly to see if there are any implementation tricks you don't know.

When to Learn Algorithms/Data structures

Next thing to come up is when in this am I supposed to learn new standard algorithms and data structures? I advise when you come across an algorithm or any other concept (maybe math idea) in an editorial you don't know about to immediately find and read an article about it, implement in the context of this problem, and then continue just moving down the problem set tab. You can usually find an article on USACO guide, cp-algorithms, or a codeforces blog. The idea behind this is that algorithms should come up at a rate according to their relevance, so if the algorithm really is important you should see it in more problems soon, and you don't need to go looking for more problems with the topic. Similarly, it is important to see algorithms in context, which is why you should not practice by topic, as you will likely miss out on many more subtle techniques and tricks not in a topics list and get too used to knowing the algorithm used ahead time when you should be trying to figure that out in the 15m thinking time.

However, if you want a break or have other extra time when you can't do problems, reading through random algorithm articles in the locations listed above is a good way to expose you to some new ideas. But it is still more important to be actively solving problems when you can.

Live Contests

The number one thing that probably looks wrong with this practice method, despite the reasonings I gave earlier, is that you seem like you are not practicing solving problems on your own often enough. This is where live contests come in. It is important to take part in as many live contests as possible from every judge you can (except ones where every problem feels too easy). This is where you practice thinking on your own, and if you look enough there are tons of contests all the time, particularly high quality ones from atcoder and codeforces. You should also upsolve the hardest problem you didn't solve during the contest, however, after that you should just go back to the codeforces problem set grind unless there are more problems from the contest within your practice rating range on codeforces. Lastly, to make sure you're taking enough contest, take every codeforces contest you miss that would be rated for you as a virtual contest.

Also, if your primary objective is some other contest (say USACO/OI but can replace with ICPC), you should do OI virtual about once per week as subtasks are becoming more important in USACO plus probably good to have more extended focus practice anyway. You also want to shift practice to doing mostly OI virtuals the week before a USACO contest begins. Make sure for these virtuals you are going for maximum points like in a real contest which may mean implementing subtasks, not just implementing full solves (or whatever other contest specific traits that differ from codeforces). If you aren't practicing a ton or you feel virtuals are taking too much time away from doing codeforces practice maybe do every other week instead of every week.

Scheduling Practice

This is less important but more just some pointers on scheduling time to practice consistently. I think it is obviously best to practice daily, and it isn't as hard as you may think it is if you build up good habits. I think it is good to have a regularly scheduled time where you can practice each day, as this makes it more of a consistent habit. Similarly, if you can set aside a specific location to practice as well that would be good, as this can give your mindset the habit that a specific time and place is for practicing only, and you build focus**.** Try to practice at least 90m for your scheduled time, but preferably longer. And get off discord!!! when you're practicing in the designated time :clown:.

Besides scheduled practice time, you can probably fit in more practice time in some or many days in different ways as well if you are serious. For example, I think it is good to memorize some problems at the beginning of each day, maybe a bit harder than you'd normally practice, and think about them all day during school, shower, eating, etc., or maybe the same problems for a few days. This helps you practice thinking more on your own. Also, when you have free time in class or while in car and someone else is driving or something, this is a good time to read algorithm articles. When I went to public school I also bought a portable keyboard to practice in class and spent most school lunch days in the library doing problems, but this might be overkill. Point is find all times of day to practice any way possible when you can, but most import is the scheduled practice time.

Outro

Hopefully this was somewhat useful to some of you, and gives you a comprehensive guide on how to practice for USACO and competitive programming in general. Please share this with others if you think it is useful.

For any more experienced people, let me know if there is anything you strongly disagree with what I said, I'd be interested to hear your viewpoint, though you're unlikely to change my mind :).

Footnotes

**I recommend the beginning of the usaco training page to complete beginners. I think it is a good way to start out as it guides you on the basics, and you should be able to start as soon as you know the very basics to a programming language, preferably c++ (you can use codeacademy to learn basics, it should take only a couple days max. you learn other parts about the language as you solve more problems and googling as needed). However, as soon as you finish chapter 1 or the problems feel easy (or if codeforces is still too intimidating maybe hard max finish chapter 2), that is when I recommend you start using this practice method, and perhaps also try some problems from the cses sorting and searching section. However most people reading this should already have some experience.

Sources mentioned:
USACO — http://www.usaco.org
Codeforces — https://codeforces.com
Atcoder — https://atcoder.jp
CSES — https://cses.fi/problemset/
Training gate — https://train.usaco.org
OI Checklist — https://oichecklist.pythonanywhere.com
Cp-Algorithms — https://cp-algorithms.com
USACO Guide — https://usaco.guide
Codeacademy — https://www.codecademy.com/catalog/language/c-plus-plus


Extra Advice How to Think to Solve Problems

Overall, just make sure you are always thinking new ideas and repeatedly combining old observations to make new ones. But for some more direct tips, try going through the following checklist when approaching a problem:

  1. look at everything from perspective of binary and graph
  2. think how information you have can be reused (like dp but more general)
  3. reduce things to as simple as possible, get rid of redundant transitions/states/etc., resolve same and induct
  4. make formulas out of everything, expand/rewrite as many ways possible
  5. visualize everything, draw things out
  6. look for structures like montonicity, concavity, etc., and do this for every part of problem, whether specific part or entire structure of solution
  7. go through testcases by hand, maybe also make generator/brute force checker if stuck to further look for patterns
  8. don't think same things over and over, write down everything you think and try to always write down new ideas, every small new observation is progress and may be able to be combined with other ideas eventually, but rethinking same things will not help
  9. think of simplified cases or imagine assuming something you wish exists already exists and solving from there, chances are thing then does exist if helps
  10. almost always a nice easily proveable solution
  11. reverse/change ordering of process or look at inverse or just view problem in different way in general
  12. if something reminds you of standard algorithm, think of every way you know how to do that standard thing and see if any modification relates to what you are doing
  13. if something seems random in statement like any abnormal constraint or is similar to known problem but different in some way, is probably key to solving so consider why it is put in statement
  14. don't forget sometimes can brute force small choices or if too many choices can pick random one or something that stands out (like max/min)
  15. don't overcomplicate. try multiple directions, if too many steps or edge cases probably not right direction
  16. restate problem/conditions in as many different ways as you can to get new perspectives
  17. believe you can solve every problem, but also treat every problem as a challenge that you take one step at a time. even most standard ideas you can learn on your own if you treat same way as any other problem.
  18. if something you remember very vaguely seems similar but you don't remember source and barely remember details, don't waste time trying to remember old thing, just start resolving from scratch

Also for debugging, just make a bunch of print statements in code and look for problems. Try to binary search and figure out where in the code the outputs are first not what you'd expect. Also try working through some examples by hand following steps of code, and read through every single line of code. It is likely the mistake is somewhere where you were sure you couldn't mess up lol.

Math + CS Practice

If you are practicing math olympiad and cs olympiad, or just want some reading material that might help you, try reading some of and doing some problems from this combo book. Overall it will be better for you to just do be actively solving more problems for cp practice, but if you have some other free time it is a pretty good read and cp is basically olympiad combo + data structures + implementation anyway.

Practicing for math olympiad in general will also help you with competitive programming, but if you are only focusing on cp it is better to just work on cp problems.

Extra Motivation

In everything in life, the key to success is learning to find fulfillment in every small step you make towards progress. Related to cp, every problem solved and every day of practice is one step closer to your competitive programming goals. When solving a problem every new observation is one step closer to finding the solution.

Also, make sure you know your priorities and what you really want out of life, don't have regrets. If you really want to be good in cp, stop wasting time, stop taking days off, start solving problems as much as you can and you will find success. Obsess over what you want most until you achieve it.


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK