Aaeria | Feb 23 2020
A lot of people didn't like the CCC last year. Lets look at the results this year...
I competed in the CCC senior division a few weeks ago. I wanted to write a small reflection and analysis here.
S1: Surmising a Sprinter's Speed
Simply sort the points and find the maximum of the speeds using the time and distance. I was scared I would make a dumb mistake and spend a long time debugging, but luckily I solved it first try.
AC in 3 minutes
S2: Escape Room
Normally s1 and s2 are trivial, so I did not expect to have to make any observations for this question. Also, the CCC grader is usually very fast. I tried a brute force dfs on the grid with up to 10^6 nodes and 2.4*10^8 edges... which recieved both a WA and a TLE. I decided to rewrite my code from scratch and think of a better method, which took some time because I became very nervous from failing the first submission. My solution was store the products as nodes, so if grid[x][y]=v, there would be an edge from x*y -> v. This way you can do dfs from node 1 to node n*m, with 10^6 nodes and 10^6 edges. I know there are many other solutions and some people managed to AC with brute force. Anyways, I spent way too much time on this problem.
AC in 33 minutes
S3: Searching for Strings
My solution was to loop through all substrings of the haystack with the same length of the needle, and if the number of each letter in the 2 are the same, the substring is a permutation of the needle. So I hashed the substring and put it in a set, and the size of the set is the number of substrings. I wrote the solution pretty quickly, but spent a lot of time fixing my hash collisions. When I get a wa i don’t know if there was a hash collision or my code was just wrong, and it took 2 minutes to judge each submission. After trying many times I finally found the parameters that worked.
AC in 50 minutes
S4: Swapping Seats
When I saw the problem I immediately solved the second subtask. The s4 last year was quite difficult so I assumed the solution this year would be very complex. I almost gave up. After thinking for a few minutes I found the answer.
AC in 35 minutes
S5: Joshs Double Bacon Deluxe
I had no idea how to solve this problem at first, but when I drew it out on my computer I began to think of my solution. Unfortunately, I did not have enough time to implement and debug my program. If I had another 30 minutes I think I would have gotten another 8 points or even solved the whole problem.
I ended up getting 60 points and 12th place. I qualified for the next round so I cannot complain too much, but I think I spent too much time debugging the early problems and did not think of the solutions for the later problems fast enough because I was nervous. I believe ccc scores do not correlate strongly with performance on cco, usaco, or most online competitions. There is only one chance to do ccc every year, so it is easy to become nervous. In addition, ccc contains a disproportionate amount of ad hoc type problems and only occasionally equires any data structures or algorithms past the beginner level. If you solved all the problems on ccc, you are crrtainly a strong programmer; however, it is very possible to be a strong programmer but mess up on ccc.
My code: https://github.com/Aaerialys/contest-programming/tree/master/ccc%20and%20cco