When I was a child, I knew software development well (though not much of C++), and my parents motivated me to try out competitive programming.
The first thing I tried was dkirienko's section. In the first 20 minutes, GCD and the Euclidian algorithm were explained, the complexity of the Euclidian algorithm was proven, and that was pretty much it. We were then asked to solve a problem set on Codeforces individually. I didn't understand much from the complexity proof, couldn't solve a single problem, failed to figure out what I was supposed to do, and left crying. So yeah, stuff like that doesn't work.
I understood simpler topics, though. I knew basic math, like how to solve linear systems and quadratic equations, and could make simple observations, so the school stage of ROI was quite easy to get through. (The hardest part was to explain to my then-informatics teacher that yes, I want the adult problems.) During the municipal stage, I had 3 hours to solve what I'd classify as a 5-task Div 3 contest. I solved the first three and stumbled on D2B and D2C. That was still a good result for my age, so I was invited to a Moscow training camp.
My experience at the camp was a bit haphazard. I didn't understand the relative complexity of the topics. Which group was I supposed to join? Was it linear and stack algorithms, segment trees, or HLD? I knew what a stack is, I wrote a stack-based parser a month prior. With some help, I figured out I should join the former group anyway.
That day, I was taught how prefix sums work, two pointers, and some stack tricks in 1.5 hours. During this time, we discussed several problems, solved them together with other students (there were about two dozen of us), explained stuff to each other, and took notes. We then spent two or three hours solving problems individually. I didn't understand all the information, but I could apply some of it to the problems. That worked.
I don't want to compare the two groups; I'm pretty sure they all had their highs and lows. I want to compare the experiences.
The way we teach newcomers at Codeforces is closer to my first experience. We tell people to solve more problems, and our only advice when that doesn't work is to read editorials. When the problems require algorithms, we tell them to read an article or two on binary search, and then come back.
Respectfully, you are all morons.
This is not how you teach competitive programming.
What got me from crying at hearing "competitive programming" to loving it was the exact opposite of your advice.
- I did not focus on ideas, I focused on algorithms.
- I did not try to solve a problem and then read the editorial when I failed, it was the opposite in 50% of cases.
- I did not go from idea-based problems to algorithmic problems as I obtained skill, it was vice versa.
- "Go solve more problems" only helped me when I had high skill, not low skill.
I hope I've explained these points below.
Start with algorithms, not ideas
Algorithms and data structures have substance. They are concrete, finished products. Compared to ideas, their limited scope:
- Makes them easier to teach, because you only have to convey a particular approach rather than a widely generalized notion,
- Makes them easier to learn, because all people have very similar views on what the topic is, so you can find a source that works best for you without worrying about losing something precious,
- Helps the teacher and the student connect because it is very clear whether both are on the same page.
Oh, but wouldn't the student not learn anything and globally applicable useful from this? That's not how it works. Your goal as a teacher is to explain the intuition rather than the algorithm itself. Instead of explaining the "what", explain the "why". If you do that, the little tricks you use to build the intuition and the intuition itself will transfer to other areas.
For example, suppose you need to give an online or an offline lecture on segment trees. You start like this:
Hi everyone! Today, we're going to take a look at a data structure called "Segment Tree".
A segment tree is like a linear array, so you can get an element by its index and modify it by index. However, in addition, it supports "range queries" of kind "what is the sum of all elements at indices between
landr":
- Get element by index (
return a[i])- Set element by index (
a[i] = x)- Sum element at range (
a[l] + a[l + 1] + ... + a[r])
Here's how not to continue:
This structure handles all these queries in $$$O(\log n)$$$ time.
Instead, you do this:
How would you handle these queries? Say you didn't need to care about performance, what's the easiest way you can imagine?
Someone says to just use an array.
That's right, we can just use an array. The first two queries will be handled in $$$O(1)$$$, but the third one is much slower, taking $$$O(n)$$$.
You draw a table with three rows and one column. The rows are named, "get", "set", and "range". The column is named "array". Complexity is written in the cells.
So this approach works fine if there are few calls of the third kind. What if that's not the case, but there were no queries of the second kind? No modifications whatsoever. You just need to sum successive elements of a fixed array. How would you solve this?
Someone says to use prefix sums. You add another column to the table, filling in rows 1 and 3.
That's right, prefix sums work in the absence of modifications. What if there were very few modifications, though? In this case, we can simply rebuild the prefix sum from scratch upon each modification in linear time.
You write $$$O(n)$$$ in row 2.
So we are clearly making tradeoffs here. Either setting is very fast and range queries are very slow or vice versa. But it turns out there's a good balance in between. The trick we'll work out in the next 15 minutes will get us to this:
Adds another column, titled "segment tree", writing $$$O(1), O(\log n), O(\log n)$$$ to the cells.
Some of you might think this is just a wall of useless text. But.
- It brings people up to speed, quickly mentioning something they (supposedly) already know, reducing the steepness of the learning curve. They aren't just thrown into the topic, they have time to recall related notions before hearing new material. This is critical in real-time conversations.
- It introduces the notion of tradeoffs. Space-time tradeoffs are easy to google; tradeoffs between different queries are rarely mentioned anywhere. Beginners need to realize that there isn't one option that fits all use cases, and it's fine to choose a solution based on input limits.
- It introduces rebuilding a structure as a viable method to handle updates. This will come in handy later when sqrt decomposition is described. Acknowledging this trick early demonstrates that it's universal, and gives participants some edge.
I could go on and give examples of how to structure written posts to utilize this approach, but basically, what I'm trying to say is that teaching algorithms does not preclude teaching useful ideas and intuition. On the opposite, it simplifies the latter, because algorithms are something you can focus on and get generic ideas from, while "just solve problems" does not give newbies the right direction.
Editorial goes first
This one's admittedly clickbaity.
During the lecture, we discussed a certain topic. We then solved a contest composed mostly of problems based on this topic. So even before reading the problem, I knew what approach I was supposed to use. I then had to find the right way to apply the algorithm/data structure to the problem, and -- guess what -- that requires thinking, the skill you all say algorithms don't help to achieve.
About 20% of the problems were something we discussed and solved theoretically during the lecture. These problems trained my implementation skills. This is something beginners often lack, and, again, many of you argue algorithms don't help train that. But I think you're forgetting that implementing the algorithms themselves trains those skills, and these skills transfer to purely idea-based problems. Hell, if I got basic implementation skills from industrial programming, they can't be that unique!
These problems let me just copy-paste my code to other problems from the same contest. No "implementing the algorithm takes 70% of the time, this isn't an interesting problem" bullshit. It was the best of both worlds.
Keep to algorithmic problems, switch to idea-based problems after gaining skill
I only had success with the "go solve more problems" approach after failing at the regional stage of ROI twice. (Though the second one wasn't that much of a failure.) I don't know if the third time's a charm or what caused me to succeed the third time, but it certainly wasn't due to how much time I spent writing contests.
During this time, I studied complex topics like number theory, Knuth's optimization, Mo's algorithm, and flows. Some of them helped me directly. Others helped me cut corners: instead of inventing a cool linear solution, I'd use a segment tree on a complicated monoid.
But many of those topics helped me indirectly. My experience in utilizing data structures helped me learn decomposition. Over time, I developed a slow yet reliable way to solve a certain kind of problems. I'd implement the stupidest solution possible and then try to fit it into TL. To do this, I looked for the bottleneck, reduced it to a single computation (preferably not related to the problem at hand), and replaced it with an alternative way to compute the same value. This could be as simple as "compute the sum via a segment tree" or as hard as "use five linear passes".
In a roundabout way, solving algorithmic problems gave me tools to solve idea-based problems I struggled to solve before because the right tool was often clear in the former case, but always muddy in the second one, until I excelled in the tool.
"Go solve more problems" is for aces
I had to solve hundreds of problems independent of the algorithms because there was nothing practical to learn anymore. With segment trees, there's a high variety of problems waiting to be approached, revealing dozens of different globally applicable approaches. With the Gomory-Hu tree, not so much.
To me, the worst part about just taking part in contests was how tiring it was. It squeezed me out like nothing else did. There was little to discuss with friends. There was no time to rest. There was no feeling of progress. Understanding an algorithm you've heard of half a year ago feels great; solving one more problem on average, not so much. If you learned an algorithm but didn't manage to apply it, you still know one more algorithm than before; if you didn't solve a problem, you didn't get anything positive out of the contest.
I wasn't prepared for learning to be this hard. This demotivated me a lot. I was knowledgeable enough to realize I was good enough to push through, but I can't imagine myself starting my competitive programming career like this, with no sense of progress and no end in sight. And now we advise newcomers to start with this?
We need to do better
We have other problems with teaching. One problem I feel like I should call out is toxicity. A person I won't name (but you all will understand who I'm talking about anyway) uses a condescending tone like this:
...we all know how to read, we have our whooping 2 month of experience! Oh, my sweet summer child, my experiments show that many people with kinda cool achievements like medals on ROI don't know how to read statements. But don't worry, I'll teach you.
...in the first damn post in the Catalog. Now, I'm not saying it's their fault for it being the first post, but do we actually want to greet beginners like that in our knowledge base?
I don't have a definite learning plan that'll get you to red reliably. For all intents and purposes, "Go solve more problems" is the best we have now, even if it's wrong and there's theoretically a much better way. I don't have time nor energy to push against the grain and prepare materials the right way, alone. The best I can hope for is to start a discussion. Grab your popcorn.
I agree with everything you said except two things:
Though there are loads of people who are unwelcoming and/or arrogant, there are a fair share of truly generous (with their time and knowledge) people. Changing this to make Competitive Programming more welcoming would mean changing the rules of the forums (no use of bad words, only pinning messages with agreeable tone, and paying people to proofread the multiple blogs in the catalog that have horrible English). That’s feasible and we shouldn’t focus on the negative. Edit: yeah I’m not really disagreeing with you now that I think about it.
« For all intents and purposes, "Go solve more problems" is the best we have now ». I don’t think that’s true, for newbies (which is >50% of the population here), the best we have (for people aged >18 (edit: for everyone, cf below)) is « attend a introduction to computer science and then a data structure and algorithms class in university ». And guess what, the way they teach you is exactly what you described in your post. Why? Because it is the best way to introduce concepts you’re not supposed to find on your own.
Thanks for replying.
A CS course in Uni is a great way if your university offers a good enough course. I believe that's not always the case. I don't have data, but it's not a universal solution by any means. In addition, many people start CP before 18 (which you allude to), like I did, so that option's out for them.
But yeah, if you can get enroll in a course like that, by all means, do that, it'll boost your skill a lot.
Harvard has an Introduction to computer science freely available on YouTube (I think 30 hours of lectures) and MIT has a Data Structure and Algorithms course (Probably around 50 hours of lectures) freely available on YouTube. Obviously, one needs to know high school maths (induction, that kind of thing) to understand those but I'd argue they're needed anyway to do Competitive Programming. Plus, those two have English Subtitles which is good for non-native speakers (it is already hard for native speakers to understand certain non-native speakers speak or write, I can't imagine what it would feel like for non native speakers / people that only learned English in middle school).
Although those courses are not tailored for Competitive Programming itself, trying to decode a blogpost on Medium written by someone that barely put any effort in it and that speaks approximate English when you are not in the top 5% of codeforces is in my humble opinion counter-productive.
We really do need to stop saying (at least for those who say "I've solved my first problem, but it's super hard, how can I get better") to just spam problems and read editorials. Following a structured way of learning CS by scholars that put hours (nay weeks) into making the most logical order of learning CS is a win for those beginners.
That's a good argument. There's also Codeforces EDU, tailored to competitive programming in particular, but it doesn't cover many important topics. Video lectures are great resources, but for good results, you need to pair them up with thematic contests (and then multithematic contests, which unite problems utilizing different algorithms, so that you learn to guess the right approach). I don't know if anything public like that exists.
Codeforces EDU seems a tad too advanced when you're a newbie. If I remember correctly, they use Radix Sort without explaining how it works (which makes sense if the public you aim your videos at is experienced). Coincidentally, Radix Sort is actually taught in that MIT course I referred. But that would be the logical continuation after attending a Introduction to Data Structure & Algorithms class.
Also, if I'm not mistaken, SecondThread did some lectures + thematic contests. I recently followed one on Treaps but there are some on easier notions.
You (or anyone else) can write pashka at any moment and offer him a new topic; then you (or anyone else) can cover it, and it will be added to EDU. Also I'm pretty sure pashka (or someone from Codeforces headquarters or community) will be ready to help with finding some problems on this topic. The current problem with Codeforces EDU is that nobody wants to spend their actual time to record lectures, unfortunately.
as CS student at big ass state university in US
I can confirm cf is way more involved than intro2cs or DSA it's bullshit btw.
I really regret not have started cp before 18. i have never seen any high-rated people who started cp after 18.
galen_colin
nah he did USACO — a hs thing
I did not mean Intro2cs and DSA for you. You are better than 75% users here. I meant for newbies who are currently discovering that inserting at the beginning of a dynamic array is more costly than inserting at the end of a dynamic array.
Hi I started cp when I was 19 and a half.
are you seriously claim that you haven't participated IOI, NOI, IMO or equivalent level of intensive training or activities before 18?
that's really impressive
Yes. I participated in the brazilian math olympiad for fun and got an honorable mention in my last year of high school but didn't study specifically for it. I did study the chapters from the math textbook that weren't used in class because I was bored though.
I started solving problems at 20 (already knew programming in general at that point) and qualified to ICPC finals from a weak university after 2.5 years. Not even a red, but something.
jiangly
I made this mistake for a long time, and by doing it on my own, no one was there to help me, nor correct me. The only way I learnt was through my mistakes, by mistakes I meant by failing at competitions. By then, it's already too late. This is why I advise anyone who starts learning (people stuck in Newbie, Pupil, Specialist, or even Experts like me), please learn it right!
Great blog! and an even better decision to leave out that person's name otherwise this blog would have been downvoted just like what happened when I called him out recently and it wouldn't get many views.
A good way(not perfect) to learn in my opinion is the same way most schools follow when teaching any subject. In competitive programming, it would be something like learn a standard topic/idea, then solve problems based on that topic/idea, then repeat the same with another topic/idea. After you do this for lets say 3-5 topics, then solve problems randomly from those topics and then repeat this whole process. I think one should do this until they cover all the standard topics/ideas required to get their desired short term rating. After that, it just comes down to simply solving more problems till you get that rating and then you repeat this process I guess.
One other important thing to note is that you can infact try multiple approaches and no need to stick to one. For instance, consider the argument on when to look at solutions. Initially, you can try the approach of looking at editorial once you are stuck for 30 minutes(Errichto's advice). If that works then great, otherwise you can switch to looking at editorials as soon as you are stuck and try to figure out what insights you could have made that would have led you to arrive at the solution(Scott Wu's advice). IF that doesn't work, you can maybe forget about looking at editorials for a month and simply solve whatever problems you can and so on. You can try them all and even if one approach works you can simply try another if you are bored of the same approach or just for a change I guess. Different approaches work for different people and any approach that helps you get better while still having fun is good in my opinion.
That's what we did in the Moscow camp (and then in Sirius, so it's not just the capital). I tend to believe that's the best way to learn too.
To be fair, that method of teaching (lesson then exercises on the lesson) is used in schools all over the world whether we are taught a new language, maths, computer science, chemistry, physics, .... If that wasn't ideal, countries would do better, they have huge incentives to make the best out of their education system.
Keep to algorithmic problems, switch to idea-based problems after gaining skillThat's exactly what AtCoder is doing, ABC contain a bunch of standard problem for beginner to learn, while ARC/AGC contain a bunch of idea-oriented problems for non-beginner to improve thinking. So I think doing AtCoder would be a good choice?
some related comment from rng_58, previous admin of AtC
Based on that comment alone (I've never participated in AtCoder), ABCs aren't made with algorithmic problems in mind. The point of my post was that algorithmic problems help people grow, so perhaps that's what we should start with.
Do you have anything except your own experience to back up your advice with?
Your a-priori reasoning is just speculation and the 1e6 nutellas who tell people to learn "ideas instead of algorithms" can also write pages of more convincing reasoning for their advice's benefits.
Also, reading the editorial before solving a problem on your own is the worst advice I ever saw.
This post took me hours to write because I wanted to capture all details I thought would be important. I don't have resources to interview others about their experiences, nor boldness to ask them to reflect on their past.
However, I think there's some things other than personal experiences in support of my theory. Russia is known to be quite great at competitive programming, and the way our largest camps teach beginners is exactly like I propose. (I only know about this in relation to school students; I think the training for ICPC is different.)
There's also a stereotype that Chinese folk know tons of algorithms, and what we learnt from them is accidental leaks, so to speak. Segment Tree Beats is one example that comes to my mind. China has great results, so it works for them too, I guess?
I said it's clickbaity. I don't literally advise that for all problems. All I'm saying is to do that for several easy problems while learning an algorithm, so that you get to know its theoretical applications and can spend some time improving your implementation skills without worrying about coming up with the solution right off the bat.
This blog is just you going "this worked for me so it is surely it is the correct way". There is a reason why high rated people have conflicting advice, people aren't "morons" for suggesting different things.
I'm sorry you read it that way. This is not what I had in mind.
I'm not saying my way is the right one. In fact, I don't even have a way, which I allude to in the closing paragraph. I'm saying that the common advice is misleading and/or useless, not that I know better.
I haven't see high-rated folk giving significantly conflicting recommendations. It all boils down to "you need to solve more problems". I take a stance with this advice. The reason I wrote this post is that it didn't work for me, but there's more evidence than that. Few organized camps offline teach students this way. This advice is dismissive and lacks substance. You can always say "you just haven't solved enough problems" to someone who failed to succeed with this advice. I'm pretty sure survivorship bias is at play here too.
It's not me going "everyone who dislikes the color purple is a moron". I have some, you know, arguments.
Basic example, Um_nik has a blog where he says that you should never read editorials. Meanwhile Benq says he frequently sees editorials and sometimes he even checks them before the problem. They're both LGMs that are top 10 in the world right now, which of them is correct? One could even argue that they're both too extreme and you should do something in the middle.
Offline camps are great for teaching algorithms, since they're short and you have a teacher who can give you the fundamentals of that algorithm. Just because camps do it, it doesn't mean you have to do exactly as they do in camps during your whole time practicing.
This strategy might have worked for you but there are also a lot of people who know many algorithms but can't solve problems. Your arguments aren't some masterpiece that back statements like "This is not how you teach competitive programming" and "And now we advise newcomers to start with this?"
People learn differently, there isn't a perfect method for getting good. The only thing that is common between all training methods is that you solve a lot of problems. That's why its the prevalent advice.
It is easy to refute your example: everything Um_nik says is bullshit and also he is rude so his opinion is automatically wrong.
The reason why they both are LGMs is simply because of their IQ. Hell, they could've switched strategies with each other and still reached LGM.
It is easy to see why Benq is smart, and I think Um_nik just got lucky when he was conceived.
The way i see it, “go solve more problems” is equivalent to “git gud”. The thing is, I would say that most of the cpers (if we exclude people from countries like Russia) are self-taught. And there are tons of resources online that have good roadmaps for beginners (like usaco.guide or cses.fi), so when someone asks for the 1000th times “how do i get good” or “how do i reach X rating”, “solve more” is just a polite way of saying “git gud”.
The “Start with algorithms” part is also controversial. I think that general consensus on “Ideas >>> Algorithms” comes from the many examples of people going “I tried to solve X using Y, but it didn’t work” or “can X be solved with Y?” It was discussed more thoroughly in this blog. The fact is, many people that are asking these questions half-learned some algorithms and then try to apply them to any problem they see, which also results in frustration when they meet conventionally easier problems that don’t use any ds or algo. I myself is an example of this situation, because I was solving 2400+ data structures problems when I was only a specialist. I don’t regret it, since it was a lot of fun to do, but encountering situations where I couldn’t solve a binary search problem in the contest while I was thinking that I’m strong because I could implement Li-Chao tree was indeed frustrating. I agree that algorithms teach you implementation skills, but you can acquire them by solving regular implementation (like the first section of cses). The only downside I see for the approach “Ideas >>> Algorithms” is the fact that we don’t have a list for these ideas, except blogs like this one.
Also, reading the editorial before attempting to solve the problem is a weird advice. If you try to solve the problem on your own first, you'll likely remember it better than if you just read the editorial.
I think the problem lies mostly with the dogmatic answers we usually see, instead of a certain approach being "right". Personally, I had the exact opposite experience you had: I tackled problems before even knowing what time complexity was, and it was fun. A lot of fun.
Again, this isn't about which one is the "better" way. I simply think that we should let beginners experiment a bit more. It doesn't really matter if a newcomer is learning new tricks or solving problems, as long as they consistently do something, they'll reach the stage where they can solve problems on their own.
I'm not sure to whom you're writing this blog. No university teacher only tells students to solve problems. The authors of "solve problems (and learn a new topic when you encounter it)" comments are not teachers, i.e. such a comment isn't about teaching, it's just a piece of advice. And it is a good advice. If you prefer the more structured way (e.g. read an algo book) then sure, it's your preference.
Your example with a segment tree actually shows that it's good to try to solve a problem first instead of immediately learning the algorithm / data structure.
This tells that you were in a decent university. My experience differs drastically. A lot of them don't care or are too insufferable to ask for an advice.
Activities for poor competitive programmers
I'm sorry if my thoughts on this blog will be a bit unstructured.
I think the main difference between examples you started with is lack of examples, simply explaining an algorithm/idea without showing how to apply it isn't very efficient.
I don't think there is a fundamental difference between an algorithm and an idea. Idea is a more specific algorithm. So learning algorithms is generally easier and more useful, but the general learning rule sounds like "learn topics in order of increasing difficulty", so it will probably favor learning algorithms sooner but not as rigidly as you seem to suggest.
Most people like us probably started learning with sections and camps (with lectures and theme contests), writing stuff like CF only for fun, not learning, and started solving problems without given topics only in preparation for olympiads. Codeforces isn't very well suited for theme contests, but there are publicly available resources for that like cses.fi, I think it's important that newcomers don't limit themselves to staying on Codeforces.
On the last topic, based on what I've seen the person you mentioned say about problems and people, I'm convinced that they have no idea how a person even of my level thinks, let alone someone from the target audience of their educational resources. People think they can get good advice from them just because of high rating which means very little in terms of teaching skill. For now I don't know of a way for newbies to distinguish good educational resource from a bad one, blog's rating doesn't work for this
I think that's a pretty good blog, I agree with a lot of your points and I haven't really thought about teaching aside from offline stuff (most of it already adheres to your advice) before
Agreed. I lot of what was mentioned in that big wall of text on segtrees are what I considered to be ideas.
We can expand on this further by considering the possibilities of doing $$$O(\sqrt{n})/O(1)$$$ set/sum or $$$O(1)/O(\sqrt{n})$$$ set/sum using sqrt decomposition. This is what I have always considered to be an idea not specific to one algorithm. It seems like the good example is the one where generalizable ideas are taught. The heading is what is very confusing to me.
Yay, another engagement bait blog! I'll bite, but first I should say:
Nobody relates to you. None. Zero people.
I think this is enough to disregard this whole blog. You knew how to code but didn't knew math, so you didn't understand why Euclid's algo is $$$O(\log C)$$$. Also it seems that you didn't really understand what "complexity" is. So you were frustrated. But then somebody gave you a lecture on an algorithm that didn't use math, and then also gave you exercises to train implementing that algorithm. And you weren't frustrated anymore!
Cool. It totally tracks. I know that I always sound sarcastic, but I'm not. When you tried to learn something that was hard for you and that relied on understanding other topics you didn't know, you got frustrated. When you listened to a lecture for which you already knew all the prerequisites, you didn't get frustrated. Then you were given exercises (not problems) and you were not frustrated again.
That's great! Your advice is great! If your goal is not to be frustrated. There is an even simpler way not to be frustrated: just don't try to do anything! Having a structured program of learning algorithms and data structures is easier than solving problems, and you have fewer chances to be frustrated. Again, I'm not sarcastic.
I'm not even sure the first thing was "just solve problems". There is a decent chance that it was the same type of "lecture on an algorithm + exercises". After all, that is how people in Russia are taught, and "dkirienko's section" is hardly an exception (said I knowing nothing about it). It just seems that you were not familiar with the prerequisites, lost the plot, and yes, got frustrated. Which is totally understandable.
What is not understandable is how you got from there to preaching "We teach wrong".
Well, lots of people come to CP knowing neither math, nor how to code. And one could argue that learning how to code from scratch is easier than learning math from scratch.
Not only does it sound a bit toxic, this also kinda contradicts the whole "main reason for doing CP is fun" thing?
I mean, even if we look at it in terms of pure efficiency, if there are several ways to learn, i believe sticking to the one that is more engaging (even if it is less effective for some abstract person) proves to be a better option in the end.
> Well, lots of people come to CP knowing neither math, nor how to code
Well, if we exclude these lots of people whose aim is to get a job, who goes to olympiads without math thinking?
I do! I improved quickly in CP without even knowing what induction was (at least until 2600 + IOI gold), and I also liked the process very much!
Not knowing != not being able to understand. Maybe you just missed an opportunity to know it.
People who can reach some heights (IOI medal, ICPC finals) all got math thinking. They are far above an average person in this component. This component is decisive in CP.
My math thinking is very high comparing to an average person, but comparing to reds it is very limited. I look at how higher rated people think and realize I can't do the same.
Nobody can prove you wrong anymore. If someone gets pretty decent in CP without math, you can say they had some secret "math thinking" in themselves that they didn't even know!
Exactly.
Maybe you misunderstand the term. I define math thinking as the ability to come up with ideas, combine them, build logical chains of them.
I'll leave an example. I'm the author of this problem. To solve it properly, you need to find an idea:
people from the same team form contiguous segments
after which the problem becomes very easy. If you can't, you suffer trying to squeeze an extra logarithm.
This idea looks obvious once you read it. But can you find it without an outside help?
I couldn't find it. I suggested this problem with an non-optimal solution. But one of the guys who is much smarter than me, could. After he said it, I immediately came up with the correct solution. This problem was mentioned in Petr's blog, so the problem of the week at least, I guess.
That's what I call "math thinking".
Upd: if there is a better term for it (maybe olympiad thinking?), I will use it.
Maybe you just need to not to talk instead of looking for other terms. Thanks.
Why u didn't go beyond master?
False premise. We don't teach newcomers at CF. We write about stuff that interests us and newcomers teach themselves.
...
I wish I knew how to read statements. Today I misread D, I thought that we'd take +max of chosen + min of not chosen.
In order to get better I mostly solved more problems with a bit of learning topics that I hadn't learned before (chosen mostly by looking at what's necessary to AC the problem I was upsolving). I already knew DP, dijkstra, dfs, bfs, etc because I started CP after learning those from uni classes so I can somewhat relate to you as well in the sense of thinking that learning those things before learning how to tackle CP problems was very useful. Some other things to point out about learning through solving problems:
go out of your way to learn stuff that you need to in order to AC problems PROPERLY as in go fucking search for other problems if it's a popular topic and solve 10+ problems about that topic just to make sure that you actually understand it after learning. If you learn one new thing per week that's already more than enough to go to ICPC WF. The only thing to polish then is your skill in those things.
seeing people skipping the process of writing their own code reference saddens me. I've gone through multiple versions of stuff like seg tree/ntt because there's a lot to optimize and also make it simpler to use for yourself in the future. Writing the data structures/algorithms that I've learned helped me tremendously in being able to adapt them to what I need when solving problems, but from what I see people nowadays just print KACTL and use that, skipping the part of understanding the finer details of stuff.
Before getting to div1 the "aha!" moments that happened the most frequent were: realizing that I don't know complexity after failing to solve some problem that's about writing 2 fors and testing everything for the nth time and binary search being fucking op. Go in depth in the things that make you fail in contests and hopefully a new thing or two sticks in you head.
Your "method of solving" of "finding correct slow solution then optimizing it" is exactly what I try to do in most problems that I'm not able to instasolve and it works quite well. I often remind people around me something like: stop trying to fit a solution into the problem, you should think of the problem then your conclusion will tell you what you need to use. Perhaps I need to emphasize the importance of actually mastering the tools that you use to construct solutions more.
As for editorials, I'm not as extreme as you but kinda close still. In my opinion if you wouldn't solve the problem during a contest you should mostly go straight to the editorial, the reasoning being that if you don't do that you probably won't go back to upsolve that problem and it'll go to waste. I've bruteforced my way through learning "harder problems" when I was cyan/expert by abusing editorials and reverse engineering the solution's ideas through reading top contestant's solutions.
The main thing in CP training is that you like the process, and the rest will come by itself!
Some controversial opinions.
CP is almost a subset of discrete mathematics in a problemsolving style. Algorithms are just tools that solve a kind of subproblem in a flash (e.g. Link-Cut Tree), not the kind of thing to practice your implementation skills and solve some cool exercise problems.
So, I guess CP isn't a good kickstart point for computer noobs, especially for those "kids dipping into the world of programming". You should have some basic implementation skills before you even start CP. For beginners with basic implementation skills, they are here to learn maths, and they should rather learn basic ideas such as greedy and BS to reach 1400 rating. Starting with segment trees that they 100% won't make use of in non-exercise problems isn't a good solution. (Though, I'm very confused about why do you promote learning algorithms to embrace one's implementation skills, given your background of software developing).
Also for the same reason, solving one more problem proves their ideas correct, while learning algorithm only give them yet another tool to use. It's easy to see which gives someone more motivation. That means solving problems is actually better than learning countless algorithms. Plus, it's more fun to try to approach the solution to one problem step by step, than to listen to a lecture and use what you learned in exercises, right? And I don't know what are "aces" in your point. Solving more problems will become almost the only way to get better at a level around 1900, which is mediocre. And I believe everyone can reach this level after a given amount of effort, not just "aces".
Contest are truly draining when I'm just hard stuck and failing 50% of the time... By the post I learned maybe I should stop going for contest and just training on my own for skills first. Fight later.
Is there any proof that hard-stuck people like myself can actually improve using any learning method? I have not followed any strict learning methodology systematically yet but this is the longest period I've ever been solving problems on a close to daily basis (2 months now, I had quit twice in the past already) and I've seen zero improvement. Certainly for me, the act of solving problems itself doesn't seem to help me improve in solving problems more effectively in the contest environment so far.
I think most top rated coders can't give good advice to the average person who is totally self taught and without any strong educational background, because most of them probably went to the best math/science schools in their respective countries and received proper instruction in math/science/informatics since a young age. 'Just solve problems' might work if you had such a background, but I have doubts that it helps for many like myself and other hard-stuck low rated users with a completely different background.
From what I've read from papers about improving problem solving, one needs to improve in two core areas:
It has been observed that to have the best success at solving problems requires a balance of both factors, because both rely on each-other. Heuristic/Strategy synergizes well with having a large Knowledge/Experience so that one can identify sub-problems easier and spend less time solving them (as the sub-problems will more often be 'Exercises' than 'Problems'). However a large Knowledge/Experience could be underutilized if one's Heuristic/Strategy is weak. For example, wasting hours to simply reduce a search space which an expert solver reduces to the solution in a few minutes.
Um_nik mostly gives advice for practicing one's Heuristic/Strategy and he doesn't give much credit to the targeted learning Knowledge while others (like yourself?) argue the opposite. The truth however is that both aspects are required. For example, the more sub-problems that are discovered and solved comes greatly from the Knowledge/Experience; and experts tend to observe what weak solvers like myself consider 'Problems' as trivial 'Exercises' because of this.
That being said, the Heuristic/Strategy does not really seem something that can be learnt easily on one's own just by solving problems. The best way to learn this would be seeing 'proof of concept' workings from an expert problem solver saying all their thoughts out loud, and explaining their solving process, but unfortunately this sort of content is very hard to find. This content does exist to some degree, and I appreciate all highly rated users that truly try to create educational content that focuses on the actual thinking process itself, but I haven't found what I'm looking for yet. Would appreciate if anyone has any suggestions for this type of content.
...your max streak is 3? with a grand total of 62 problems, only 18 of those being rated 1200 or higher? I'd say your rating checks out.
Apparently you've never heard of a problem archive before. I usually do not submit outside of contest unless the problem can only be submitted from outside vjudge. I've solved 1000s of problems outside of this platform and cannot improve my success in contest (I solve a few easy ones and then get stuck for the entire contest on a brick wall).
ggs, that came out way too judgmental. Sorry about that.
Is it possible for you to somehow share the set of problems you've solved on vjudge (idk how vjudge works)? For a very long time, I've been a firm believer in the idea that if one solves enough problems, they'll get better sooner or later; your situation is very surprising for me. Are you sure you don't spam easy problems during practice? Do you panic during contests? Is there any difference between the difficulty of problems you solve during contest/practice, and the time you spend on them?
The more blogs like "how to become cool in CP" I read, the more I think that everyone should come up with their own way to do it.
I agree. at first I constantly read editorials after like 10 minutes of thinking and found myself improving quite fast, and then after reading um_nik's blog I started not reading editorials and trying to solve problems for a longer time, and at that time I didn't improve at all, and now im back to reading editorials, and I think i'm getting much better. I really don't think there is one way to improve for everyone, and everyone should try out multiple ways and find what suits them best, instead of arguing which one is the best objectively
Is this a new ACC?
idk what you consider new, i made this acc 3 months ago.
Your first account
oh, yeah
How did you do this impressive work within that short time wow
having a decent math background helps, and also just being consistent
what math background do you have?
NICE.
I very strongly disagree with this idea, and think it's dangerous to promote to noobs. I think you can find most of my reasoning in my practice blog. But particularly, it is very easy to get used to only knowing when to apply algorithms in textbooks situations and get used to not thinking for yourself if you start by only learning textbook stuff. This is more true than competitive programming, you see this with the majority of people in school who go through a bunch of classes and being unable to solve any problems outside ones that fit the templates they see in class. I think classes taught like this generally are very bad, and think at least the US k-12 education system taught like this sets people up for mediocrity at best.
However, it is true that there is slightly more to "just solve more problems". I believe for efficiently learning to practically use most topics, you need to both "just do more" and "reflect heavily what you did verse what you could do better". The people who fail when "just solve more problems" usually do so because 1. they don't like to think hard as um_nik described or 2. they just memorize/move on after each problem and don't reflect how to generalize their thinking process.
In similar line, I think "formalization is the death of intuition" is fairly truly, but more particularly "learning formalization before intuition will prevent you from ever gaining intuition, but intuitively realizing how to formalize yourself shows true understanding".
As long as you force yourself to truly focus and think hard then reflect on how to generalize to future as much as possible, I think you'll improve no matter your specific practice method. However, if we want to promote a near-optimal practice method, it should be one that sets people up to think hard and reflect, which I believe learning to memorize and apply textbook algos to template problems does the opposite.
Reflect == ?
Being able to understand where your thinking process wwent wrong if you werent able to solve a problem.
lol
Ivan purplesyringa Machugovski, I strongly disagree that we should start with algorithms. I think ideas should come first since all algorithms are based on some ideas. It's like building a tower without building it's base first.