Sorry for the long break. I returned here. This post is just about analysis of my personal performance.Last Sunday, the last Open Cup round of this season has finished. Except for GP of Japan (I chose some problems from old AtCoder and translated them), there were 17 rounds and 191 problems in total. That's a lot of problems, given that few problems are very easy. I solved 143 of them. That means I couldn't solve 48 tasks - let's take a close look at those 48 tasks.
First, I define "objective difficulty". When N teams participate and x teams solve a certain task, the AC ratio is x/N. However, it seems when small number of teams participate, the average level is higher. Thus, I defined the difficulty as x * sqrt(100 / N). Usually the number of teams is around 100, so this value should be close to the number of ACs.
My results are:
| Difficulty | Problems |
| [50, inf) | 95 / 95 |
| [40, 50) | 8 / 10 |
| [30, 40) | 17 / 21 |
| [20, 30) | 8 / 13 |
| [10, 20) | 11 / 20 |
| [5, 10) | 4 / 9 |
| [0, 5) | 0 / 23 |
Not surprisingly, it shows a very strong correlation.
And here's the complete list of those 48 problems. From left to right, it shows contest ID, contest name, task ID, task name, number of ACs, number of participants, difficulty, topic, and "the room of improvement". Topics may be inaccurate because I don't know the solutions of some of the tasks. Three or more stars mean that I feel "I should have solved it during the contest!" (five-star tasks are the most serious ones).
| 14 | Tatarstan | I | Minimum Prefix | 42 | 76 | 48.18 | strings, flow | ☆☆☆☆☆ |
| 16 | America | G | Apple Market | 41 | 95 | 42.07 | flow | ☆☆☆☆ |
| 12 | Wroclaw | C | Game | 34 | 79 | 38.25 | graph theory | ☆☆ |
| 17 | Moscow Workshop | B | Completely Multiplicative Function | 34 | 89 | 36.04 | number theory | ☆☆☆☆☆ |
| 17 | Moscow Workshop | C | Even and Odd | 33 | 89 | 34.98 | graph theory | ☆☆ |
| 18 | Ural | M | Maximal Paths | 32 | 88 | 34.11 | tree DP, implementation | ☆☆ |
| 15 | Three Capitals | B | Book Pages | 34 | 136 | 29.15 | ad hoc | ☆☆☆ |
| 14 | Tatarstan | B | White Triangle | 22 | 76 | 25.24 | geometry | ☆ |
| 4 | Eastern | K | GCD on the Segments | 26 | 108 | 25.02 | data structure | ☆☆☆ |
| 10 | Gomel | E | Exclusive Training | 26 | 112 | 24.57 | data structure | ☆ |
| 11 | China | I | Prime Tree | 31 | 192 | 22.37 | graph theory | ☆☆ |
| 15 | Three Capitals | I | Puzzle with Tables | 21 | 136 | 18.01 | constructive | ☆☆☆ |
| 9 | Peterhof | E | Maharajah | 17 | 90 | 17.92 | brute force | ☆☆ |
| 3 | Spb | C | Number of Solutions | 19 | 161 | 14.97 | exponential | ☆☆ |
| 16 | America | B | Stars in a Can | 13 | 95 | 13.34 | geometry | |
| 15 | Three Capitals | E | Cross on a Plane | 15 | 136 | 12.86 | geometry | ☆ |
| 13 | Poland | H | Matching | 11 | 80 | 12.3 | graph theory | ☆☆☆ |
| 2 | Eurasia | H | Multiplier | 21 | 313 | 11.87 | brute force | ☆☆ |
| 2 | Eurasia | A | Maximum Sum with Swaps | 18 | 313 | 10.17 | DP | ☆☆☆☆☆ |
| 12 | Wroclaw | J | Explosions | 9 | 79 | 10.13 | math | ☆☆☆☆ |
| 18 | Ural | I | Intricate path | 8 | 88 | 8.53 | constructive | ☆☆☆ |
| 10 | Gomel | A | Ascent Sequences | 9 | 112 | 8.5 | combinatorics | ☆☆☆ |
| 16 | America | F | Incremental Double Free Strings | 6 | 95 | 6.16 | DP, implementation | ☆☆ |
| 11 | China | H | Order-Preserving Partition | 8 | 192 | 5.77 | combinatorics | ☆☆☆☆ |
| 13 | Poland | A | CNF-SAT | 5 | 80 | 5.59 | strings | ☆ |
| 17 | Moscow Workshop | F | Online LCS | 4 | 89 | 4.24 | strings | |
| 11 | China | C | Power of Power Partition Function | 5 | 192 | 3.61 | combinatorics | ☆☆☆☆ |
| 14 | Tatarstan | G | Milkland | 3 | 76 | 3.44 | geometry | ☆ |
| 15 | Three Capitals | G | Pigeonhole Principle | 4 | 136 | 3.43 | interactive | ☆ |
| 13 | Poland | B | Almost pattern matching | 3 | 80 | 3.35 | strings | |
| 18 | Ural | F | Flight Trip | 3 | 88 | 3.2 | interactive, geometry | |
| 8 | Europe | D | Dancing Disks | 3 | 98 | 3.03 | constructive | ☆ |
| 11 | China | A | Almost Bobo Number | 3 | 192 | 2.17 | strings | |
| 10 | Gomel | I | Inversions in Lexicographical Order | 2 | 112 | 1.89 | FFT | ☆ |
| 2 | Eurasia | D | Park Trails | 3 | 313 | 1.7 | data structure | |
| 2 | Eurasia | L | Give the Parabellum away | 3 | 313 | 1.7 | geometry | ☆☆ |
| 11 | China | D | Line Counting | 2 | 192 | 1.44 | number theory | ☆☆ |
| 12 | Wroclaw | E | Inconvenient Blockade | 1 | 79 | 1.13 | graph theory | |
| 16 | America | I | Ski Resort | 1 | 95 | 1.03 | graph theory | ☆ |
| 8 | Europe | G | Geohash Grid | 1 | 98 | 1.01 | implementation | |
| 10 | Gomel | C | Cyclic Shifts | 1 | 112 | 0.94 | strings | |
| 5 | Siberia | J | Battle City Online | 1 | 119 | 0.92 | brute force | ☆ |
| 3 | Spb | I | Double Shuffle | 1 | 161 | 0.79 | ad hoc | ☆☆ |
| 4 | Eastern | J | Votter and Paul de Mort | 0 | 108 | 0 | geometry | |
| 8 | Europe | I | Invisible Integers | 0 | 98 | 0 | DP | ☆ |
| 9 | Peterhof | D | C-plus-minus | 0 | 90 | 0 | data structure | |
| 12 | Wroclaw | K | Bridges | 0 | 79 | 0 | ad hoc | ☆ |
| 13 | Poland | D | Mushrooms after rain strike back | 0 | 80 | 0 | data structure |
I know I'm bad at several types of tasks - for example, long implementation, advanced knowledge, etc. However it seems I failed quite a bit of problems of my strength - math, combinatorics, DP, etc. My skill of competitive programming has plateaued 6.5 years ago, but still there's lots of room for improvement.
I'll upsolve all tasks with 3 or more stars, and hopefully some of 2-star tasks.
