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.

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.