ICPC Regionals Singapore 2015 Review

The contest was held 2 days ago. This time, our team, JustBrowsing, did not do as well as the preliminary round nor what we aimed for, solving only 3 problems during contest time and coming in at rank 30+. Somehow, for the problems we attempted but could not solve, either we could not make the observation or we could not figure out the missing piece of the solution, such as how to do a certain part of the solution efficiently. The good thing was, with some strategy and luck from the circumstances(almost every team was attacking the easiest problem), we managed to win “First to Solve” for a problem(prize was power bank). The following summarizes what happened for each problem.

A. Association for Cool Machineries(Part 1)
At first glance, I was thinking of something along cycle-finding via simulation but had no idea how to do it. My teammates attempted this problem at a later time but we still could not solve it as we seemed to be missing out on some possible cases from what I heard(I could not understand their discussion). Turns out to be some Depth-First Search(DFS) thing, which I have yet to understand nor figure out an implementation.

B. Association for Cool Machineries(Part 2)
We already cannot solve for the previous problem, so this problem was ignored.

C. Association for Control Over Minds(solved during contest)
This is the problem that we were the first to solve. While I was reading the description for problem A, a teammate already read and figured out how to solve this problem already. Looking at the scoreboard, no one has solved this yet, so we might have a chance. He went on to make a submission for this problem and got us our “First to Solve”. This problem can be solved using Union-Find Disjoint Set(UFDS), augmenting with an array that tracks size of each set(updated at the “root” of each set) though our team used something similar but different. I did not read nor think about this problem so the UFDS idea came from other teams after the contest(I later implemented this and make a submission in the open contest).

D. Association of Computer Maintenance
I concluded that the problem is about finding 2 factors of a number such that the sum of the 2 factors is minimised. The solution involves partitioning the prime factors into 2 partitions and then doing something like a O(N log N) search to find the best pair. The problem was that I could not find a way to do the partitioning correctly so I had to give up on this problem. The presented solution uses a different partitioning scheme and the purpose of partitioning is different from mine as well.

E. Association for Computing Machinery(solved during contest)
This problem was the easiest problem since it has the most number of teams getting AC early in the contest. It uses a greedy solution by placing the problem to be solved as the first and sorting the rest by time taken. The maximum number of AC can be obtained using a linear scan and the total penalty time is the sum of the time at which the problem was solved. I could get the maximum number of AC correct but I totally did not understand how the penalty time works from the sample input as I never delved into the scoring system for any contest. Thankfully the rest of the team could understand it, helping us get another AC.

F. Air Conditioned Minions(solved during contest)
Another not-so-hard problem. Represent each interval as a pair. Sort the pairs. Do a linear scan, maintaining an interval that is in all the pairs processed so far. Increment the answer when an interval does not overlap with the maintained interval. (I had to ask my team on how to solve this easy problem so I definitely did not code this during contest.)

G. Association for the Country of Mubaba
The problem we tried for so long but could not solve. The sample test cases tricked me into thinking that it can be solved using a greedy linear pass. A teammate managed to come up with a counter-example to convince me that it is actually DP. For the remaining time, we we trying to formulate the correct DP but failed. After the contest, a solution I got from another team was: given the starting point of the previous subarray and the current position, the current element can either be given to the previous subarray or form another subarray whose sum is greater than that of the previous subarray. Use binary search on the prefix sum array to check if such a new subarray can be formed. The solution runs in O(N2 log N) time. Checking by linear scan will give O(N3) time which will get TLE. Turns out we got our state parameters right but failed to make this observation when computing the states. I only got the implementation for this solution right recently.

H. Association for Convex Main Office
We are bad at Geometry problems so this problem was skipped. Discussed solution involves forming triangles of different gradients(base and height of the triangle must be co-prime to achieve this). No idea how to implement this as the full solution is not disclosed.

I. Apples, Cherries, and Mangos
This is clearly a combinatorics problem. Simple DP does not cut it due to the problem size. Turns out it involves using some formula which we could not derive as none of us are good at math(by Math I mean Number Theory, Combinatorics, etc., not the JC level of computing summations and integrals type).

J. Association of Cats and Magical Lights
Another problem where I have no idea how to solve but my team has some idea. The missing portion is to query for number of magical colors, as well as perform updates efficiently.
Shared solution: Use DFS to map every vertex in the tree to an index. Evry subtree is thus a subarray. Use arrays to track which color is at which vertex and Fenwick Trees of parity bits for query and update since the problem is only interested in odd/even number of vertices in subtree with a certain color. I personally never thought one can use so many Fenwick Trees…

J. Association of Camera Makers
This is totally out of our league. The shared solution can only solve 10 out of 16 test cases due to problem size. The actual solution requires reading up some research papers…

Thanks Lim Yu De and Le Beier for contributing to the discussion of solutions. I doubt I can solve even the 3 that we have solved during contest time since my problem-solving thinking is still not very good nor am I experienced enough to make any key insights. Hope this post has been useful.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s