Since this December, I've been exploring codeforces data to answer the question of how best to improve your rating. Today, I'm presenting to you all the final project!

The first problem in trying to do data-driven analysis is trying to get data. Codeforces does have an API, but it's quite difficult to get data from it at a large scale. So first, I cleaned everything up and created two big datasets, and I've published them to kaggle. So, if you think my analysis is garbage, you can download the dataset yourself and try it yourself!

Dataset: The submissions and contests results for 60k recently active users

Dataset: The final standings for every codeforces contest

After getting the data, I began doing analysis and creating some charts. I looked at a lot of features, such as first solve time, rate of getting incorrect answers, and the difficulty of problems. For many of the features, I could not find great insights, but there are still quite a few interesting graphs in here! I hope you enjoy this data analysis that I've been working on for the last 3 months!

Click to view the story

Here I've enumerated some of my favorite problems. The solutions appear trivial in retrospect — but the 1 line observation is quite hard to come up with. You have to think really outside of the box for these! I think such problems are quite cool and hard to come by, so please add a comment if you have any other problems of this type that you've seen!

They are arranged from easiest to hardest (in my opinion).

1) For $$$N<10^6$$$, what's the Nth palindromic number in base 10 with an even number of digits? (The first is 11, then 22, 33, 44, 55, 66, 77, 88, 99, 1001).

Key observation:

Source: https://mirror.codeforces.com/contest/688/problem/B

2) A classic: $$$N < 10^6$$$ Ants are on a line of length $$$10^{15}$$$ at some positions $$$p_i$$$. Each has a starting position and direction left or right. They walk at a rate of 1 unit per second, and if 2 collide, both immediately turn around and walk the other way. How long will it be until no ants are on the line?

Key observation:

Source: https://mirror.codeforces.com/gym/102966/problem/G and other places

3) $$$N<10^5$$$ Rectangles with ODD side lengths are on a $$$10^9\times 10^9$$$ grid. The corners of each are at integer lattice points $$$(x, y)$$$. Color each of the rectangles one of 4 colors so that no adjacent two rectangles are the same color.

The four-color theorem shows that this is always possible, but provides no further insight for this problem.

Key observation:

Source: https://mirror.codeforces.com/contest/764/problem/D

4) You've got three $$$3000\times3000$$$ matrices $$$A, B,$$$ and $$$C$$$ containing only the elements 0 and 1. You need to output a boolean: if $$$AB=C$$$ with all elements of $$$AB$$$ taken mod 2. Note: Your method must work with high probability on ALL possible inputs. Maybe a lot of people want to hack your code.

Solutions that won't work:

Key observation:

Source: A class in complexity theory

After a long time of trying to solve this problem, I was excited to finally have a solution that seemed to work.

I quickly submitted the solution, but to my great surprise, I obtained a TLE. I quickly searched through the code for anything suspicious, but I could not find anything — it seems to be very clearly O(n^2), with n at most 5000... but it still takes far too long: running it on my computer it seemed to take more than 1 second for the loop where I simply initialize all the values to Infinity!

Does anybody know why it would take so long to do such a simple task as this? What am I missing here?