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.










Monday, February 13, 2017

Best Performance and Worst Performance

After the last blog, I participated in three contests: GP of Gomel (tourist's contest), SRM 708, and GP of China. The problems were very nice in all contests and I really enjoyed them. However, my performance was quite different: in SRM everything went very well and it was my best performance after the last TCO, but today I performed terribly (well, 17th in Open Cup is not bad, but given that the problems really suited me, it was terrible).

In SRM I was in a very strange situation. A few minutes before the end of the coding phase, I found that my solution may access to out-of-memory and fail. However, it worked on random tests and I decided not to resubmit - and luckily, it passed the systest!

In GP of Gomel, I solved seven tasks (B, D, F, G, H, J, K) quickly and I still had two hours to solve something else. In such situations, I usually read all problems and sort them by expected difficulties for me. The difficulty is estimated by the number of ACs (objective difficulty) and the topic (for example, I'm good at combinatorial/mathematical tasks, but bad at data structures). For me the topic is more important and after spending several minutes on each task I decided to concentrate on A and I because they looked the most interesting for me and no task was solved by many people - however I couldn't finish coding I in time and ended up with nothing.

In GP of China, after solving five tasks (B, E, F, G, J), I had more than 3 hours. Among the remaining tasks, I liked C/D the most and decided to spend 3 hours on them, but again ended up with nothing.

It seems I can quickly solve easy problems, but when the problems become harder I can't do anything. I seriously need to fix this tendency. Maybe I should try Div2 in next Open Cup? Anyway, I will upsolve at least four tasks (Gomel's AI, China's CD) in the near future and post here again. I believe I understood the solutions for these tasks now and they are indeed very nice.