The ACM ICPC Singapore Regionals Preliminary Contest happened last Saturday on 12 September 2015. This was my 2nd official contest that I joined, the first being NOI 2010. Our team JustBrowsing, which consists of myself, Le Beier and Lim Yu De, came in 20th(rank 6th among Singapore teams), solving a total of 6 out of 10 problems. It was pretty good, considering that we were just trying to see where we would stand since it was our first time participating.
Before the prelims, we made it a point to practice once every 2 days so that we would be in good shape for the contest, but due to NUS class workloads only Yu De (being in Tokyo for an exchange programme) could practice frequently. As Yu De was in Tokyo during the contest, we were the only team to be Skyping during the contest 🙂 Still, it was a good test of our problem-solving and implementation skills.
Our strategy was simple: Beier will read all problems and try to solve them (but not code them as Beier was not confident in implementing) in order of increasing difficulty, starting from the last problem and ending at the first. Yu De, our strongest member, will try to solve(and perhaps implement and AC) as many problems as possible, starting from the easiest. If any of the implementations would take more than just a few minutes, they will explain the solution to me(hopefully I can understand) and I’ll implement it while they move on to tackle harder problems.
Problem A (ICPC Tutorial) was easy but jumping in to the code immediately turned out to be an unwise decision as we found ourselves with 6 WAs and TLEs before AC, all due to silly mistakes like forgetting to break, and checking a condition before actually multiplying (for factorial). Problem B (2048) was slightly more tedious to implement compared to A. While Yu De went on to debug these 2 problems(turned out to be implementation bugs), which he eventually AC-ed, it was my turn to implement and submit our solution for Problem I (Pivot).
Problem I was another simple problem: given the state of the array after 1 pass of partitioning(refer to quicksort), how many numbers could have been the pivot for the partitioning process. One of the assignments in CS3230 was about good and bad numbers in determining whether an array is sorted. Using this idea, I know that if a number is a pivot, it must be a good number(in the same place if the array is sorted). However, the implication does not work the other way. Beier reminded me that for any pivot, all numbers to the left must be less than the pivot and all numbers to the right must be larger than the pivot. So the largest of the numbers on the left side must be less than the pivot and the smallest of the right side must be larger than the pivot. This reduced to a static range max and range min query, with the starting points being the leftmost and the rightmost elements respectively(Implementation details omitted for brevity).
Problem C (VisuAlgo Online Quiz) was just a direct Dijkstra’s algorithm which requires some augmentation to track the number of shortest paths. Thankfully, Yu De knew how to code it(I had no experience in counting shortest paths) and got AC in just 1 try. This brought us to a pretty good position at that time if I remember correctly.
Problem D (Grid MST) was an interesting variation of the standard Minimum Spanning Tree(MST) problem. No edges were given and the number of points was very large. The straightforward solution is to form a complete graph and then run Prim’s/Kruskal’s algorithm. However, this will easily get TLE. Beier initially came up with some kind of solution but sadly, I was unable to understand it so he had to discuss it with Yu De so that Yu De could implement it instead. Turns out that we needed some way to reduce the number of edges processed before running the MST algorithm and we became the first to solve this problem after 4 tries. Even till now, I have yet to figure out the solution that Yu De implemented for this problem(patly also because I did not have the time to read the editorial).
At this point, the next 2 to solve would be H (Panda Chess) and J (Animal Classification). At first, we thought H was edit distance, but the edit distance algorithms was O(n^2) DP and since n was 10^5 this was not feasible. Yu De noted that this is a permutation (because it is a ranking) and the problem reduced to Longest Increasing Subsequence (by ranking) , with the answer being 2*(number of pandas – LIS) after using topological sort to get the rankings. We were plagued by bugs due to not having enough experience with the O(N log (LIS)) algorithm, and also missing out corner cases such as when some pandas do not exist. At least, for some reason, toposort to get the ranking was very swift and easy :). Got AC after 6 tries. Ouch, our time penalty is really heavy now.
At this point, we had seen all problems and we knew that D (Rectangle Land) was a very tedious segment tree problem and that F was probably impossible for us to solve (we do not have very strong mathematicians).
After that, I went on to stare very hard at Problem G (Ski) while Yu De went on to solve Problem J. Due to the fatigue at that time and our inexperience at hashing algorithms, Beier and Yu De concluded that to pass the time limit we needed to merge nodes in O(1) time by hashing but we could not come up with a good scheme. The idea of binary hashing scheme with multiple prime modulo only came 5 minutes after the contest ended. So unfortunate.
For Problem G, after some hard thinking, the only valid subsolution I managed to come up with was to find the rightmost point given the cost(I did not know how to do that efficiently though). My subsequent ideas of the optimal solution involving both highest and lowest points turned out to be wrong as Yu De was able to come up with counter-examples. Turns out that my idea for the first step was correct and needed to be implemented with the technique called “Binary Search the Answer” to find the rightmost point that the skier should stop. As for the remaining part of the solution, it involved using Segment Tree to find the maximum range sum in a given range. This was not something we had encountered before, let alone implemented. So we were unable to solve it during contest time.
Glad that we could advance into the actual Singapore regionals this December. I realised that Binary Search the Answer and Segment Trees are very useful in many problems, from past contests like Google Code Jam and Codeforces contests. The only thing stopping me from improving this semester is being bogged down by NUS modules, especially CS3216… I hope that we can get a decent ranking in the upcoming regionals. Till then, I hope to have some time to brush up my skills when the exams are over.