What does efficient “PRACTICE” really mean in Competitive Programming?

Revision en1, by acraider, 2023-08-04 02:54:00

Have you ever wondered what are top performers doing better apart from just putting hours and solving problems??

Read this whole and you might just get a new perspective on what can “Practice” really bring to you… or how should you target one. A little on Pedagogy side, but I hope it will be an interesting read.

I am very happy to get more suggestions, as these are personal learnings that I have noticed in the last 4 years of actively teaching others Competitive programming, DSA, and working on pedagogy and gamification aspects of trainings.

Well, Lets start with a hard fact…

Solving problems beyond a certain level actually requires you to have at-least these 2 things: 1. A decent IQ and Maths Skills. 2. Good “Practice” with an intent to abstract.

Let me explain you what these 2 mean, from best of my knowledge. I will focus more on the second one though…

  1. Have a decent IQ and Maths Skills.

Ofcourse till a certain level, it’s just about “practice” and knowing coding language (Implementation Skills), but as you start growing beyond say 1800-2000 rating level, its really starts sharply hitting you.

You need Good IQ and Maths skills to be really at the the top. Strong Knowledge of Counting, Number theory, Geometry, Probability, Linear algebra starts getting asked in problems and you always need some Good IQ to start generating good observations and connecting the dots to things you might have learned in the “Practice”.

Well this blog is not on this point, so I will keep it till this and not digress much. After all, your time is precious! So keep reading.

  1. Intense “Practice” with an intent to abstract.

Ok, I agree that it’s a sentence with a lot of buzzword-y terms, but it all will make sense soon.

So you practice to improve right?

Try to seek answers for these yourself: 1. How do you select questions that you are going to practice? 2. What are some objective takeaways from any problem that you look for? Or are you just trying to memorise the solution of that exact problem? 3. How do you ensure that you learn and retain maximum from a problem?

Have you ever thought about these or it has been just been

Well I don’t think pedagogy ever has been taken seriously in a field like CP. It has mostly been people who are subconsciously doing these are improving and rest are finding it difficult.

So what’s the solution Vivek ???

I am no expert on the same, but over years what I have realised is what learners are picking up from practice can be classified into one of these 4 Categories. 1. Concept 2. Tactic 3. Form 4. Framework

Before I explain them, quick question. Have you ever played MMORPG / RPG Game? (I expect all of you to say Yes… expecting all of you to be geeky gamers like me in old days :P)

Back in my childhood, I used to play a lot of them. In fact design many of them using 001GameEngine.

When you play a RPG game, a typical setup is the following 1. You are at Level 1. 2. You choose certain monsters / perform some quests. 3. These give your some Drops and XP. 4. The more XP you collect you level up. 5. The Drops give you Special Weapons that have certain types of stat point. 6. As you progress you start seeing harder monsters, for which you have to strategise on which weapon to use. Say there is a water type monster and you know that Fire weapons will work much better on them.

I feel problem-solving in general is exactly like this. More so in CP.

  1. You start with basic language implementation skills (Level 1)
  2. You chose Problems (monsters) / Topic Questions (Quests)
  3. Each problem drops builds some Concept and Frameworks (XP) and teaches some Forms and Tactics (Drops)
  4. As you see harder problems, you use your Concepts and Frameworks (XP) to strategise an attack and use the tactics and forms (Drops) you have collected overtime that best fits.

Hmmm… quite similar right?

Let’s now understand what these are and how can they be truly used.

Concepts : These are fundamental Algorithmic pieces that you learn (little theoretic) that are used directly to solve or code standard problems.

Eg. DP is a simple memoization concept over what you have learned on Backtracking. You learn how to code basic idea too in this.

Framework : These are first level questions you ask yourself as you see a problem to decide what can potentially be used. Asking good questions to yourself can be key in solving problems.

Eg. “This Is a Tree problem and we need to do counting. Can we use DP to solve it? Some maths maybe?”.

If gives you the path to progress in a problem, so that it’s not haphazard.

Form: Standard class of applications that you see in a particular type of problems.

Eg. Most of tree-dp (Which itself is a Form) problems generally fall in one of these subforms. 1. Maintaining parent state with a state. (Whether the parent was taken or not). 2. Merging subtree contributions. (Like some knapsack on each subtree). 3. Maintaining full ancestral states (Like GCD of root till this node).

Usually this is something that you pickup when you see a lot of problems of the same type.

Tactic : These are independent ideas that are generally used to reduce/solve the subproblems or optimisation issues.

Eg. Say we have a knapsack type solution where we merge DP(node,Items taken in subtree) for a Bunch of Childs. One tactics that exist that reduces this from O(N^3) Dp to a O(N^2) dp is that when you are merging the child’s dp value, merge small to large sort ( maintain the current size and only update potentially till cur_size+new_child_size in the dp table).

Now if you don’t know this tactic, there is no chance you can solve problems that need it. [If you don’t, learn it from here : https://mirror.codeforces.com/contest/816/submission/37993710]

These are the primary 4 things that you should focus on when you are practicing.

Want to see another example of usage of this ? Just made a video explaining the same too : https://www.youtube.com/watch?v=F2HgeehAaio

Now ofc you might ask me Vivek.. Ok, that’s all good, but what should I do now??

Improve your practice !!

Most students who comeup to me and ask me that ‘why are they not improving from a very long time ??’ … mostly the issue is with one of the following.

  1. They are not practicing.
  2. Their practice strategy is absolute garbage.

You will not be able to improve in a game 1. If you keep defeating simple monsters much lesser than your level. 2. Defeat a monster and then leave the DROP and XP you should have gained (very very common). You will Never improve.

Your goal while solving any problem shouldn’t be to ‘memorise’ how to solve ‘this’ problem, but ‘analysing’ what can you actually ‘take away’ from this that you can use to solve something in real contests.

How to actionably do this ?? Post solving a question, just retrospect what where the new 1. FRAMEWORK question you picked (How would you think about something like this next time ?). 2. CONCEPT you learned (Go to some site and learn it). 3. FORMS you have built (Collect problems of similar type and see what are you using in them repeatedly), 4. TACTICS used that you can pickup (See for optimisations and observations).

If you are seeing a lot of problems in practice that is leading to no new thing in this list, your practice (sorry to say) is bogus.

If you are seeing too many in every problems, then maybe you collect them (which is difficult to be recalled), and requires too much of mana (I think I should stop playing game :D)

How to choose problems that will give you more of them… or how to work on the memory recall part of it ?? well that’s hard and I will keep it for another long blog (It has been more than an hour of me thinking and writing this… sorry).

If you read till this, it on its own means 100 upvotes for me. Looking forward to your take in the comments :D. If more people like these take, I will write more things on the pedagogy side. See ya in the comments.

TL;DR: Please don’t be at the bottom of this pillar.

Tags practice, improvement, pedagogy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en13 English acraider 2023-08-04 03:45:19 0 (published)
en12 English acraider 2023-08-04 03:40:52 8
en11 English acraider 2023-08-04 03:39:59 50
en10 English acraider 2023-08-04 03:37:47 455
en9 English acraider 2023-08-04 03:23:46 6
en8 English acraider 2023-08-04 03:21:32 74 Tiny change: ')\n\n![ ](https://mirror.codeforces.com/1cd303/rpg.jpeg)\n\nBack ' -> ')\n\n![ ]()\n\nBack '
en7 English acraider 2023-08-04 03:17:11 28
en6 English acraider 2023-08-04 03:13:43 60
en5 English acraider 2023-08-04 03:13:34 157
en4 English acraider 2023-08-04 03:01:19 93
en3 English acraider 2023-08-04 02:59:50 322
en2 English acraider 2023-08-04 02:55:28 73
en1 English acraider 2023-08-04 02:54:00 8350 Initial revision (saved to drafts)