Our 2015 Southern Africa ICPC Regionals is nearby, and we have been using some of the 2013 SA problems for training purposes as well as a teaser/taste of what’s to come on the 24th of October (registration closes on Oct 10). While the training materials are on vula (the UCT CMS for courses), some hints to solve some of them may be of general interest. I’ll give a breakdown and a ‘spoiler alert’ for five of the eight problems. The problem-solving aspects and explanations in the training sessions were longer, but these short notes will give you some useful starting points where to look for implementation details already anyway.
The problems can be categorised into the following types:
- Isle of the birds – computational geometry
- Fitness training – simple ad hoc
- Similarity – String processing
- Railways – Graphs
- Student IDs – String processing
Isle of the birds
There’s an island with trees, and the rubber band will enclose them all. That is, we need to find the polygon with corners of the outermost points enclosing the rest of the points. Thus, we need to compute a convex hull. How can that be done, and, more importantly, how can that be done efficiently? Computing the whole solution space is going to take too much time, as there can be between 3 and 15000 points. One technique is the sweepline (generally useful to check out), and one of those tailored to finding the convex hull is the Graham Scan algorithm: first, starting with the left-lowest point, scan the plane of points counter clock-wise to figure out where the points are (points on the same line are ignored), then, second, connect the points in a stepwise fashion from the bottom going counter-clock-wise again: if the angle is >180 (compare values of the coordinates), then discard the penultimate point and connect the 2nd last to the last point.
Only 4 teams solved this problem at the 2103 regionals (including the winning team ‘if cats programmed computers’).
John cycles A km, Mary runs B km, starting and finishing at the same place using one circular route of M km. This can be computed with a straight-forward modulo operation. All 53 teams solved this problem at the 2013 regionals.
Spellchecking in the online search engine; well, given two words, what is the minimum cost of the change operation to go from word_A to word_B, given certain costs of additions, deletions, and character swaps? Comparing strings of characters is around quite a while, from spellchecking, to plagiarism checkers, to DNA sequence alignments, so surely a fine algorithm should be around for that already. Indeed: the minimum edit distance (Levenshtein distance) (nice explanation), where, instead of computing all possible options (very costly!), you fill in the table accordingly. The ‘tricky’ part is that the basic algorithm for the minimum edit distance counts each change as a cost of 1, whereas in this problem, some changes cost 2; hence, you will have to change those values in the standard algorithm (demo that lets you play with different costs).
Only 2 teams solved this problem at the 2103 regionals (including the winning team ‘if cats programmed computers’).
Construct a railroad network between cities in the shape of a tree, but put in a bid for the second-most cheapest option. So, we have lines and points, or: some graph algorithm. Two main groups are shortest path (Dijkstra, Bellman-Ford) and spanning tree. We need a minimum spanning tree (MST) to begin with. This reduces the option for the most suitable algorithm to Prim’s or Kruskal’s. Prim requires a particular starting vertex, Kruskal doesn’t. The problem statement doesn’t require a starting vertex, hence Kruskal’s algorithm is the one of choice (example). But then how do we get the second-best spanning tree? Also in this case, many have asked before (thoertically and practically—search online for both): take an edge with weight w that’s not in the MST and results in a cycle when added to the MST, compare w with the weight of the heaviest (non-w) edge in the cycle (v), then of those comparisons among the cycles, take the one with the lowest difference, add the edge with weight w and remove the other edge v. There you have your second-best option.
Only 4 teams solved this problem at the 2103 regionals (including the winning team ‘if cats programmed computers’)
Generate student IDs from the students’ names, following a given pattern. Of itself, this is a somewhat laborious implementation. The only real issue is to keep track of what’s been processed of the string. Here, it is especially useful to first design the solution separately before delving into the murky code, as it otherwise will require a lot of test cases to check the corner cases (and remember you have only one machine). A nice way to design it is to use automata and only then to convert that into code.
39 teams out of the 53 solved this problem at the 2103 regionals.
Just in case you’re trying out the remaining problems, and are banging your head against the wall or pulling your hair out: no team solved the Street lights (Problem B; looks like a maths problem, with floating point complication) and the Necklace (Problem G), and only 3 teams solved Matchstick maths (Problem D; ask a team member of ‘if cats programmed computers’, who solved it).