Wednesday, May 3, 2017

Summary of Open Cup 2016-2017

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.










5 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Thanks for the analysis.

    I wish so, so much I could participate in these contests... How can I do so? Thanks!

    ReplyDelete
    Replies
    1. As far as I know, you can't without an account at http://opencup.snarknews.info/~ejudge from a registered university sector.

      Delete
    2. And how do I get one? :)

      Delete
    3. If you can go to one of the existing sectors, it's easy to participate. Otherwise I think you need to contact them with email (you can find the email address at opencup.ru).

      Delete