Competitive Programming: Talent vs Tenacity
How does practice affect contest results?
Many programmers try their best to prove themselves in programming interviews, but a few aim to go beyond just 'good enough to be hired' and prove themselves in an ultra competitive setting.
While leetcode and hackerrank are big names for beginners practicing, competitive programmers tend to favor other websites.
The popularity of these competitions has been growing over time.
Masters in these sites can consistently finish 'competitive programming type problems' orders of magnitude faster than even experienced programmers, in addition to having the expertise to solve more difficult problems.
But before we get there, we've got to start small. Let's start your journey by solving an introductory problem!
Every problem gives you a specific amount of time and memory for your code to execute. If you can't solve it in this time, you'll get no points.
Next, you get a description of what the problem entails.
Each problem has a very well defined values that the input can take, and often the challenge is in solving the problems for very large inputs. You may have had an idea for how to solve this problem for n up to 10000, but after reading this bound, it clearly won't be fast enough. How can you handle such huge values?
Finally, you have some samples to test your solution on. There are also many hidden cases on which your solution will be exhaustively tested.
It's estimated that people with a rating of 1000 have a 50% chance of solving this problem in a 2.5 hour contest.
Most problems will have a heavier algorithmic component than this one. Here are the most commonly found algorithms in codeforces contest.
If you weren't able to solve the palindrome problem, don't worry: that's quite typical for a new contestant. This graph by nagitosu shows that 1000 is the most common rating. On the other hand, less than 10% of people have a rating above 2000.
One way to measure the amount of practice that someone has put in is by counting the number of correct submissions they have on codeforces.
Want to see where you are? Codeforces users can easily check the number of problems solved on their main profile page.
It's worth noting that many people compete or practice on multiple sites, so they may have many more submissions than this data implies.
Let's at least try to eliminate a few variables and find out why some people are learning faster than others. Instead of looking at the final rating, let's consider the change in rating.
Click the labels to filter out participants at that rating level.
There are still many people who have solved a lot, but still don't see much improvement. Maybe the reason is because they only solve easier problems, so they don't learn anything new.
It seems that solving hard problems seems to have a more significant effect than solving easy ones. But how well exactly does it work? Using a two variable linear model, we compare the effect of solving a problem at or above your rating ('hard') and the effect of solving any problem below your rating ('easy') on the change in your rating in a year. What do you think the best coefficients were?
(Hover over the information icons to find out)
n_hard_problems * ???? + n_easy_problems * ???? ≈ rating change
Surprisingly, not only does solving easy problems not help improve your rating, it even correlates negatively with it! It would be very dubious to claim that you actually get worse by solving easy problems, more likely it is just an effect of the correlation between people who solve high proportions of easy problems not growing as fast as those who mostly solve hard problems.
One might suspect that the phenomena would only appear at lower rating levels. Here is the line of best fit for each rating distribution.
So, do easy problems ever have value? It's often thought that solving easy problems can help improve your speed.
Overall, there is a positive trend with correlation .37 between the number of easy problems solved and the first solve percentile, while the trend only has a correlation of .09 with hard problems, indicating that there is some truth to this statement.
However, we should treat this with suspicion. I also tried estimating the change in first solve speed after a year [a very noisy estimate, as it is attempting to estimate the change of averages of few data points]. In this setting, there was actually more correlation in first-solve-speed improvement when solving hard problems in this setting.
What should I do now?
Based off of the data here, it is best to focus on solving problems that are challenging to you. People who tend to try solve problems that are easy for them do not do as well as those that challenge themselves.
If your goal is to gain 200 rating in the next year, a more measurable goal that may lead to the approximately the same outcome would be to solve 200 problems above your rating level in the next year.
Considering that hard problems can often about 2 hours to solve, and assuming that most people do about half of their practice on codeforces, one might estimate that it would take about 800 hours of practice to gain 200 rating. That's 20 weeks of full time work!
With this estimate in mind, consider carefully your goals: is the benefit worth the amount of time you put in? Unless you're passionate and having fun, it likely is not.
That said, there are many different types of problems, and some people will be be more interested in ICPC contests or marathon problems than codeforces competitions. If you just focus on one aspect, you will grow much faster!
Sources
Problem credit: Problem https://codeforces.com/contest/688/problem/B by Mohammad Mahdi Shokri and Parsa Abdollahi.
Cover, Image 1, final image: ICPC Global
Stats Cliff image: Lovepik
Project done for CMU "telling stories with data" class. Assignment writeup
Code background image: It's a screenshot of a particularly unreadable submission on codeforces
Built with Shorthand