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.