If you are triggered by this clickbaity blog title, you are probably interested in improving your Codeforces skills. Now, I will share my point of view on the differences between Codeforces and ICPC contests, and how you can, in my humble opinion, maximize your Codeforces rating gain.
I mostly consider that all conceivable competitive programming problems need three aspects of skill:
Observation — the ability to understand the problem and come up with non-trivial properties.
Technique — the ability to apply a well-known algorithm or data structure to the problem.
Implementation — the ability to code fast and debug fast.
Collaterally, I refer to these three skills as Russian-ness, Chinese-ness and American-ness, respectively, for reasons you will soon see below.
Observation (Russian-ness)
Observation means that you stare at some problem for a sufficient amount of time and you are able to reduce it to some easier problem. One good problem that I think is interesting is this 1889D. Despite being rated 3000, the problem is solvable in 30 lines of trivial code. Of course, there are also bad problems, such as the infamous 1916D and 1916H1, but the gist is that the problem needs good mathematical thinking and nothing else.
I consider this aspect of difficulty to be Russian because this type of problem happens more often in Russian ICPC-style contests, specifically OpenCup and ICPC camp, etc. They are also single-handedly the most popular problem style on Codeforces and AtCoder.
Now the interesting part about it is that since the skill level correlates to math skill and nothing else, you can literally do IMO problems instead of Codeforces problems. For instance, if you take this problem list from IMO2022 and look at the combinatorics problems in it, you will see that they translate nicely to Codeforces Div. 1 problems. There is a saying that math majors have an advantage over CS majors in Codeforces, and I think it is justified to some extent.
Technique (Chinese-ness)
Technique is the more common thing you will learn at any competitive programming course, such as binary exponentiation, segment tree, etc. Obviously, it is not fully possible to distinguish techniques from observation, but I draw the line as to whether it is possible to produce a reference code for the thing in question. So dynamic programming and greedy are more Russian, and Fenwick tree and segment tree are more Chinese.
Now I call these problems Chinese because Chinese OI and ICPC have a tendency to produce problems that are solvable only by advanced data structures that are only possible if you have a reference code. For instance, 104857C is solvable only with a palindrome tree, and 104857A is solvable only if you took some graduate course.
I guess this is the most learn-able part of all, and what most learners of competitive programming will engage with. Now we get the intuition why it is so hard to improve at Codeforces: you are trying so hard to become Chinese instead of becoming Russian!
Implementation (American-ness)
Implementation mostly refers to problems that take a lot of time to implement, such as geometry problems that are very popular in US contests, such as 104757C from the recent ECNA. I mostly consider that there are two difficulties in implementation. One is that the code is just long but is not particularly tricky, such as the famous Rubik's cube; the other is that the code consists of many cases and is hard to get right, such as 104869I.
Now I call these problems American because geo problems usually require a code reference and are pretty popular in US regionals.
Summary
Now, where does Codeforces stand in all of this? I will make one bold claim here: for Codeforces now, you only need Leetcode medium + high school math contest to get to blue. I will try to argue for it in these two claims.
Claim 1: You only need to finish Div. 2 A, B, C in one hour to get to blue.
This is trivially true by looking at past contests.
Claim 2: Div. 2 A, B, and C require nothing but basic programming skills and good math skills.
This is more debatable, but I think none of them require any noticeable techniques other that mathematical analysis. Therefore, being good at middle and high school math contests suffices.
Now we can answer the golden question of all time.
How do I improve at Codeforces (for now)?
A lot of people in Codeforces Catalog will just say that you should do more problems. That is obviously true, but it reminds me of this interesting joke:
Why learn swimming? Just jump into the river. It works for everyone who lives after that!
I think, ultimately, this line of thought just loses people out of competitive programming for thinking that they are not clever enough. I hope this blog convinces you that Codeforces for people below Div. 1 has nothing to do with programming but everything to do with math. Therefore, to study for Codeforces you should not study programming but instead study for math contests!
Why haven't I become better at Codeforces after reading through cp-algorithms?
Because Codeforces has nothing to do with competitive programming algorithms for people below Div. 1. Just study math problems instead!
Should Codeforces be so 'Russian'?
Now, obviously, it's not for my humble mortal mind to ever contemplate the masterful design of Russian grandmasters such as 74TrAkToR. But I think, in general, when a problem that has a higher Chinese difficulty is proposed, the response is
This problem seems too standard (translate: is not Russian enough). It would be a good one for an educational round, but not a regular one.
As for American-ness, well...
When was the last time you saw a geo problem in a Codeforces contest?
Jokes aside, it is beyond me to say what should be more important in competitive programming contests, but I do think the community should reflect on this interesting difference between Codeforces and ICPC.
Alright, now, before I got nuked by the three largest countries of the world, canceled by the greatest grandmasters on Codeforces, and downvoted to oblivion, I think it is high time that I bail out. I will end with this sentence.
May the Russian-ness be with you.
Auto comment: topic has been updated by Zhtluo (previous revision, new revision, compare).
Auto comment: topic has been updated by Zhtluo (previous revision, new revision, compare).
Auto comment: topic has been updated by Zhtluo (previous revision, new revision, compare).
Auto comment: topic has been updated by Zhtluo (previous revision, new revision, compare).
so if I marry an American, get my child to have a kid with a half Russian half Chinese & maybe some slav for good measure, that child will go on to become the greatest competitive programmer of all time.
No because the child will still have your genes
i am never making another comment on codeforces again
Nice. You are Accomplishing your Goal by a Hole.
Actually the Russian-ness Chinese-ness American-ness sort of thing is mostly related to cultural differences, so moving to Russia is a better choice.
What an Extraordinary, Mind blowing Fantastic thoughts.
Awesome blog, cool analogies!
I think that I should improve my observing skills immediately, because I always come up with a worng assumption and firmly believe it's true.
So if you find the problem unsolveable with your assumption, you can try to change your mind. It often works!
I appreciate problems with high observation difficulty. But "Chinese-ness" and "American-ness" is a must as it's a great loss for people who are intelligent enough to observe some important properties in certain problems but are unable to solve them (in time).
True. But there are also math contests, and whether CP should be like math is debatable.
I will also argue that in real life software engineering it is preferable to have high American-ness.
Getting better at Russian-ness will definitely improve your Codeforces rating, but I'd like to point out an interesting take that improving at American-ness will probably have the same effect as well.
With good American-ness you can "speed" through the easier problems, which gives you higher odds of having your rating increased (and even be a huge edge in so called "speedforces" contests) while leaves you with more remaining time during contest to work out the harder problems. Pair this with constantly spamming div4/div3 contests (with lots of implementation problems) and you have the perfect formula for reaching blue ;)
My Chinese-ness fr not helping me get higher rating even if I know how to solve Div 2. E problems using segment tree.
ORZ can solve div2E
wtf i can’t even solve div2d in contest
yeah div2e is easy i solved ike 50
Maybe? But getting stuck on Div. 2 C is not very enjoyable...
I agree. It is so frustrating! I can solve the first 2 problems easily, but the third problem hits me hard...
So can I say there will be more Ad-hoc problems (I mean the problems that don't have the same difficulty to everyone) on Codeforces and Atcoder because of their "Russian-ness"?
I live in America and my parents were Chinese, yet I do better on Russian codeforces than on American USACO. Hmmm...
Because you're USACO Plat and built different.
maxrgby orz
Main problem is u don't have 1 billion point on rise of kingdoms
This blog is so accurate especially about Russian-ness. One of the editions of ["The USSR Olympiad Problems Book"](https://www.isinj.com/mt-usamo/USSR%20Olympiad%20Problem%20Book%20(The)%20-%20Shklasrsky,%20Chentzov,%20and%20Yaglom%20(1993,%20Dover)%20(1-1).pdf) comes to my mind.
The introductory problems section just looks like straight Div2B/Div2C problems. Some of them might-be brute-forceable but proof wise they feel like Div2B/C's.
Problem number $$$3$$$ is Tower of Hanoi, that too generalised for $$$n$$$ discs. The book is meant for middle-school students interested in math competitions. I don't understand how those middle-school students are doing recursive/inductive proofs of this kind at such young ages. But, I'm pretty sure such students shoot straight to expert on codeforces under ten contests after they've learned STL and Binary search.
This other Russian book: Mathematical Circles has such a significant resemblance to codeforces style problems, I used to end up contemplating atleast once every month, about whether I should take the plunge and spend my time doing these type of problems.
But, it feels risky to make math the primary training. There is only so much time one has, what if the carryover isn't as much as I'm thinking it would be. Do you recommend going for such problems or trust the codeforces problemset archive to show you whatever kinds of problems you need to solve ?
Thanks for the blog.
I don't understand how those middle-school students are doing recursive/inductive proofs of this kind at such young ages.
I think young kids are generally more capable at learning such ideas than most people think. Unfortunately due to such biases most are not exposed to abstract ideas as young as they should, and don't have as much time to ponder and sink in when only exposed older.
Love the star wars reference at the end 8)
There are many times when I come down to a conclusion or observation but that particular observation isn't the one needed to solve the problem, which makes me angry.
And finally when I see the editorial its another problem with some basic observation/constraint which is actually making the scope of the problem very small and easy to implement.
I don't know when I will be able to make correct observations 90% of the time, but would keep grinding.
And I won't compare Leetcode to CF, I sometimes complete all 4 leetcode contest problems in 1 hour and here in CF only C takes sometimes more than a hour :(
Nice blog. Good insights.
Pretty cool blog, In your opinion what could be some of the ways to increase one's Russian-ness being in a college?
Interesting! I have sometimes seen people saying that Chinese problems are more algorithms-heavy (I do not necessarily agree), but I have never thought about the other two. I did not think I was biased, but maybe I am. But I feel like the observation part is actually pure problem-solving, no? For me, heavy implementation and applying algorithms is like fluff on top of problems. But making observations and inventing new things is actually the essence of problem-solving in my opinion. Whenever I need to think for hours to solve a problem, but then the actual code is 15 lines, I am amazed. That is the pure joy of solving problems.
Maybe. But problems like 1916D - Mathematical Problem doesn't give me much joy, so maybe we also need some other metric.
Meanwhile, doing things like Rubik's cube seems fun, despite not really Russian problem-solving.
Idk the problem you are referring to but obviously, I am not saying that all problems that follow such a trajectory are good. I am just saying that for a problem to be good, it should probably have the observationism in my opinion.
IMO a good problem strives for all three.
I think the main point of debate is whether the problem should have more observation than the other two, as CF currently is.
But obviously how Russian a problem is is pretty subjective...
I am also biased since I do better with American problems ;)
When I saw a problem and its solution I think "wow it's so cool" "I don't come up with the brilliant idea" "I'll share it with my friends". But after they saw the problem they said "it's a typical problem" "I've solved it two and a half years ago" "totally an old trick". It's "Russian" for me, but "Chinese" for them.
My problem with algorithm-heavy and implementation-heavy problems is that solving them feels more like a craft. Something one just masters through pure repetition. But observation-based problems are about exploration, invention, creativity, and all the other things that cool kids do :)
Funny. My coach's advice for solving observation is to go through a bunch of math problems and books...
Which I feel is too repetitive and boring lol.
For the Mathematical Problem, I think it's about observation, but it feels more cheap to me. In my opinion, observations which are easily found by looking at a bruteforce feel a bit cheaper than genuine insight which you can't really find just by pattern matching on small cases. It doesn't feel that creative as some idea which you by more abstractly reasoning and thinking about the problem.
every enjoyable problem is russian by that metric
Re: LLL (104857A), this is actually a very common and well known algorithm for a lot of cryptography and specifically for cryptography CTF challenges. You definitely do not need to take a graduate level course to have solved this problem, many high school students who are avid CTF players use LLL all the time on challenges.
I do CTF myself. I am somehow not convinced that 'many' high school students understand the mechanics of LLL...
Well, at least not as many as high school LGMs. :)
This is not a joke, I know some who are just mediocre in algorithmic skills but superior in mathematical ability, and they are consistent purple, sometimes yellow
I don't think such users are uncommon either
What would you define as being good in math? Is it just good in mandatory studies at school or higher like getting a medal in math olympics?
No ADHD. Ability to focus on one thought for a prolonged period of time, watch how it unfolds without forgetting the previous thoughts. Big enough short term memory, so that it can fit large enough context. You cannot solve problem, if you forget the sentence that you read 10 seconds ago. Fast associative cache memory, so that you could quickly recall some information by getting certain keys while reading the text or having certain thoughts. Thoughts generate some kind of hash keys. If you don't have an association at the time when you had a thought (hash key) you will not be able to make a mental jump and continue thought exploring the space of possibilities. This often happens to me, for example, I need a lot of time to populate my cache in my brain before my thoughts could produce meaningful jumps. If the problem is trivial you can solve it by brute force just by pure thinking (if you have long enough thinking context window), but this is not the case in 99.999% of the problems. You almost always need some kind of associations to make mental jumps when you generate new hash keys during thinking process.
I think this is not a very hard requirement, just makes you faster than others at solving problems (and does not, at least noticeably, affect the solvability of problems for you). As a kid I was definitely able to hold many more ideas in my head than I am able to now, but now I have both experience and the common sense that ideas can be written down on paper if they're overflowing from your short-term memory. Note that this is just about the process of solving problems. For storing ideas and making connections, you definitely need a stronger set of connections in your mental graph to be able to fetch those connections quickly, but as for storing ideas you produce in real-time for a specific problem, it is not of primary importance. Sometimes I forget things relevant to the problem that I thought of 10 seconds ago, but I still end up doing research-level deep thinking about those problems successfully all the time. For me, the crux is to be able to internalize intuition about results rather than bombarding my short-term memory with stuff I could have written on paper.
Association Is All You Need: Brain & Transformers Work The Same Way — short 5 minute video
Yes ADHD Makes it difficult.thus no self attention and no big context that is proven to effective in solving problems by transformers.
This blog is helpful for the contestant who are beginner or under div 1. We want this type of blog again. And Thanks for this blog.
I think it's all just about IQ and thinking ability. In my opinion you can't improve this things with practice or anything else (study math, learning algorithms, solving math problems). All of these (Russian-ness, American-ness, Chinese-ness) related with each other if you good at observation than you almost certainly good at other things as implementaion or advanced techniques and vice versa.
I think, ultimately, this line of thought just loses people out of competitive programming for thinking that they are not clever enough.Yes, people lose out on competitive programming because they're not as talented as others. Studying math won't make you good at observation if you don't have a high IQ or talent.
finding observations is the distinctive skill, not everyone can have that
I think the need for reference code is somewhat overestimated for "implementation" and "technique" problems.
Surely, it is beneficial to have a code reference for many algorithms and data structures, but I also think that just superficially knowing the algorithm and maybe having implemented it once or twice before is sufficient to use it without a reference?
For geometry, most "primitive" stuff (intersections, etc) is not that hard to deduce ad hoc if you have a notion of how to reason about them efficiently (when it's better to use a parameterized form vs equation form, etc).
Palindromic tree is also quite simple in itself and has a concise implementation which is very similar to Aho-Corasick (which, in turn, is just Knuth-Morris-Pratt algo on a trie). I guess you might want a reference for its advanced applications (e.g. breaking the string in a concatenation of the minimum amount of palindromes which requires non-trivial usage of "series links"), but the core functionality hardly needs a reference if you already have an idea about how it's typically constructed.
Generally, I feel like the shift in meta to learning so many algorithms as "black box" without learning how they are actually implemented is quite recent? I didn't have any team reference document in my active ICPC years, and I don't really recall any cases when I really needed it. If I needed to code a suffix automaton, or a persistent segment tree, or an FFT, well, I just did that "here and now".
This is not to brag, of course, but just to explain that in my years, I took it for granted that you're expected to know not only how to use an algorithm, but also how to implement it. But these days I keep hearing things like "oh no, this problem requires fft, we shouldn't use it in a contest that doesn't allow TRD, no one would be able to implement it" and it always catches me off guard, because I'm so used to seeing (and often solving) such problems in contests without using any TRD.
At some point, I understood aho-corasick very well and could easily implement it. After 3 months of not using it, I couldn't.
I heard some rumors (not sure if it actually happened) that during some onsite contest, a team consisting of Petr and two other top-rated coders couldn't solve the problem because it required FFT, and nobody in the team knew how to write it.
I personally always used FFT just as a black box, which multiplies two polynomials, and never was able to implement it during the contest in a reasonable amount of time. But I always had teammates who could do it, so we never had a team reference book :)
Even in math, there's still a difference between "Russian" and "Chinese" problems which you can easily see just by looking at the China TST.
sir then please suggest some math resources , how can we improve in mathematics stuffs
Fun fact: the authors of the "most Russian" problem (i.e., 1889D - Game of Stacks) are Chinese.
XD
Cheating (Indian-ness)
interesting article. You come to the same conclusion Geothermal does in https://codeforces.com/blog/entry/118882
You are based beyond belief. I had fun reading this, it made a lot of sense to me.