How to train: why it's not enough to just do a lot of tasks

Правка en6, от Wind_Eagle, 2022-04-03 23:51:17

Hello, Codeforces! I, like many of you, read blogs periodically. Lately, blogs from low-rated users who ask me how to raise their ratings have been catching my attention. I want to tell you a little bit about my opinion on these blogs.

So what do these blogs look like? Usually this is a blog with a title something like "I need help right now!" or "How to improve my rating, help me!" When you open this blog, you see the most detailed description of the problem, such as: "I have solved 500 problems, but no improvement" or "I have solved 100 problems with rating >= 1500, but my rating is not increasing". And in the comments they usually write "you haven't solved enough, solve more" or "solve more difficult problems". In my opinion, this is incorrect and misleads such users.

So, imagine that you do not know anything at all about sports programming, or even about the basics of Olympic math. You at best (because many people don't even do that) have learned a programming language at a basic level (really, who needs templates and classes), such as C++. And so, you decide to become a sports programmer to get a job interview enjoy solving interesting problems. Imagine yourself as this person. Can you? No, imagine please, it's important.

When you have imagined this, imagine now that you have no friends at all who know what programming is. "Programming, huh? Is that edible?" Well, I'm kidding, of course, but it could very well be that no one around you is into programming. So, now there is a question. How to improve?" "What's a stupid question?" — you ask, "of course, just go and solve problems!" Just everything, and maybe some ladder (which I don't know much about). So, I declare: in my opinion, this is very bad advice, which will only harm someone who starts his way in sports programming. You have imagined yourself as a beginner, haven't you? Now think about it: if you only know high school math, can you solve D2A? If you think you can, I'll let you in on a secret: if you are not a born genius in sports programming, you probably can't.

Let me tell you a little about why. As can be seen from my profile, I'm from Belarus, from the city of Mogilev. In this glorious city there is a glorious gymnasium number two, where my wonderful EIK teacher teaches. She has many Olympiadists, both beginners and very experienced, like Dmi34, and a bunch of experienced, among them, for example, me, as well as another international master and international grandmaster. And I can tell you: if you take the beginners now, I'm not sure that they could solve even D2A in the first year at once. I'll explain why.

The whole point is that even D2A should actually be approached gradually (unless, of course, you have experience in math olympiads, say — then solving D2A in general is not a bad idea). Back to our mental experiment — take any random D2A from the last two years.

Totally randomly I chose round 672 and Problem A from it (1420A - Cubes Sorting). Think about it: How easy is it for someone who only knows school math to solve this problem? For example, in our university department we have a small section (for one or two lectures) devoted to permutations, and from this knowledge it is easy to solve this problem. But if you only know school math (and you have an ordinary, unremarkable school), then solving such a problem will obviously not be that easy. Actually, understanding that an unsorted array can be sorted by a bubble sort in n * (n-1) / 2 operations is not that hard, if you reason logically. As I see it, it is harder to show that for an unsorted array this does not hold.

Or round 697, problem A (1475A - Odd Divisor). Of course, this problem can be solved by simply writing out all the numbers on a piece of paper and finding a pattern. But here you need to know what is decomposition of a number into prime factors, know that it is singular, and so on. Thinking back to the greedy algorithms, I can mention the problem from round 765, problem A (again chosen at random) (1625A - Ancient Civilization).

My point is this. You need to know mathematics for sports programming. Now imagine: someone has solved, say, 100 problems A. Consider that most of them do not contain any new and interesting ideas at all, but just, as they say, ad-hoc. So what will one learn from these problems? I'm not sure, but it seems to me that simply nothing! One will remember twenty ideas, but the twenty-first will still be different. Going back to our imaginary newcomer: he has no one to ask, no one to ask to explain. No one to explain the standard ideas and approaches. So what does he have to do but cheat to write blogs?

The situation with problems B, C, and D is even worse. To solve them, you usually need to already know the standard ideas. The problem is that in order to practice these standard ideas, you need to solve problems on these standard ideas, not immediately D2C — D2D. Imagine if you were learning a segment tree right away from a 3000 difficulty problem. That's not very good.

To conclude the first part of the blog: Codeforces — is definitely not a place for beginners to practice. While more experienced users can practice here, it is hardly suitable for beginners. What to do, I do not know, and why I do not know, I will explain later.

Now let's move on to the second part. Now I want to explain why I think the Codeforces complexity approach is a bad idea.

Let's take a look at a few (again, totally randomly chosen tasks). Let me tell you right away: this will be my subjective opinion. Let's look at problems 858B (858B - Which floor?) and 996B (996B - World Cup). I consider the first one very simple for its complexity, and the second one — very difficult. I solved both problems long ago, but I only remember that when I was a pro, I solved the first one, although with difficulty, but when I was a candidate master, the second one was very difficult for me — I don't even remember if I solved it or not!

This is not to say that the tagging system on Codeforces is not very good, and often confusing. For example, in the DP topic you may come across a prefix-sum problem, and in many tasks the tags are put on the principle "here is a problem on ST/DP/bit operations. But it can be solved with flows. Let's put the tags: graphs, flows. Oh! You can also use ternary search! So let's do it!" So tags really don't always reflect the topic of the problem.

My point is this. You have to train by theme (but tags are also broken), not by difficulty. Especially when you're not that experienced yet. Don't be afraid that you can't do ad-hoc tasks — the main thing is to be good with standard ideas.

Many commenters who write "solve more problems" have, in my opinion, simply (and that's okay) forgotten what it's like to be gray or green. And that's okay: I don't remember solving while I was down, either. But looking at the way my instructor has been giving exclusively standard problems and approaches for a year or two, I'm starting to realize that she's probably doing it right.

Going back to our example — how would such a person know which topics are standard and which are not? At most he can only know the names of the topics. And by the way, apparently, this explains so many gray people who learn the Cartesian tree and Mo algorithm — they don't quite understand what things are needed at what level. And why don't they understand? In my opinion simply because there is no one to explain. So if you're a newbie/pupil and you're reading this, know — you need to learn approaches, not algorithms. And algorithms are better not to learn, but to understand. You should probably learn an algorithm when you encounter a problem at least once/twice in which you can bring the solution to completion, completely and independently, if someone had written the algorithm for you. That is, you have thought up all the steps, all the math, reduced the problem to a well-known algorithm — then you can open it and try to understand it. By the way, if you can't understand it, you can learn it for now — it seems okay to me. You can go back later for understanding (when you have more experience). When I was an expert, I didn't understand the segment tree (really, I was a high school student then, and not even a senior).

So, smoothly passing to the main idea of this blog — I can't imagine how you can practice without a coach. Of course, when all the basic ideas are studied, and the algorithms are perfected, you can move without a coach. But, say, to an expert or even to a candidate master will be much harder without a coach. I know that there are a lot of people who have studied on their own, and reached the heights. It seems to me that you — this is more of an exception to the rule than the rule. I'm very glad that you're doing well. But personally, I realize that without a coach, my progress would have been much slower.

I know that if people who came here to train for interviews. Guys, this is not the place for that at all. That's what LeetCode was invented for — there's a bunch of great problems to prepare for, I've solved a dozen or two myself.

Lastly: in my opinion, Codeforces should decide: should it still be a training ground for beginners, or should it only be a training ground for more senior ranks? Because if it's supposed to be a training ground for greys/greens as well, it doesn't seem to be. Because Educational rounds aren't Educational at all, they're regular Div. 2 rounds, which are only slightly more standard in terms of ideas and approaches. Even Div. 3 rounds, which are designed for greys and greens, have recently started to contain ad-hoc rather than standard tasks again. I understand that this is done for ranking consistency. But let there really be simple tasks for newcomers. In the Edu section there are problems on standard algorithms — believe me, learning these algorithms won't do much good for gray or green.

Therefore, if one wants to create a more favorable environment for beginners, make separate, perhaps unrated, practice rounds. I understand that a lot of effort is put into each Codeforces round by the authors, coordinators, and organizers (myself the author of two rounds and co-author of another one). Maybe that's why Codeforces will probably remain what it is. And you know what? I'm only going to be glad. Surely (but I don't know for sure), there are plenty of places for newbies to train. Let Codeforces remain as great as it is now, with ad-hoc challenges. In my opinion, that's what makes the rounds so interesting and exciting (just please don't make all the tasks on one topic. I won't give you examples, but there are some. Believe me, it's not cool).

Thank you Codeforces for being there!

Теги traning, rating, pikachu, codeforces

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский Wind_Eagle 2022-04-03 23:51:17 31
ru10 Русский Wind_Eagle 2022-04-03 14:52:57 0 (опубликовано)
en5 Английский Wind_Eagle 2022-04-03 14:52:51 0 (published)
en4 Английский Wind_Eagle 2022-04-03 14:52:35 88
ru9 Русский Wind_Eagle 2022-04-03 14:51:26 67
ru8 Русский Wind_Eagle 2022-04-03 14:49:30 68
ru7 Русский Wind_Eagle 2022-04-03 14:48:50 63
en3 Английский Wind_Eagle 2022-04-03 14:47:57 58
ru6 Русский Wind_Eagle 2022-04-03 14:47:46 65
en2 Английский Wind_Eagle 2022-04-03 14:46:25 124
en1 Английский Wind_Eagle 2022-04-03 14:28:43 10873 Initial revision for English translation (saved to drafts)
ru5 Русский Wind_Eagle 2022-04-03 14:25:42 21
ru4 Русский Wind_Eagle 2022-04-03 14:24:48 70
ru3 Русский Wind_Eagle 2022-04-03 14:18:30 18 Мелкая правка: 'ых, вроде Dmi34, а также ' -> 'ых, вроде [user:Dmi34], а также '
ru2 Русский Wind_Eagle 2022-04-03 14:17:23 135
ru1 Русский Wind_Eagle 2022-04-03 14:15:40 10677 Первая редакция (сохранено в черновиках)