Contest Report


Problem A: Another Convex Polygon Problem

This problem is a straight-forward application of a polygon clipping technique. The easiest way to solve it is to keep a list of regions (which are all convex polygons). Then, for each line, the intersection with each polygon is computed and, if the the line crosses the polygon in two distinct points, the polygon is split into two other convex polygons.


Problem B: Breweries

In the computer science literature this problem is called the weighted K-center problem on a tree. The author's solution has time complexity O(N*log(Cost)). The maximum cost is binary searched. Then, for each value of the Cost, chosen during the binary search, a value dmax[i] = Cost/B[i] is computed, meaning the maximum distance at which a brewery may be located away from city i. Then, the tree can be rooted in node 1. Traversing the tree from the leaves towards the root, a greedy algorithm can be used in order to place the minimum number B of breweries satisfying the dmax[i] constraints. If B <= K, then a smaller cost may be chosen; otherwise, a larger cost needs to be considered. The greedy algorithm works as follow: for each node i, two values are computed -> dist[i]=the distance to the closest brewery placed in i's subtree ; maxd[i]=the maximum distance away from node i at which the nodes in i's subtree (including i) may accept that a brewery is placed; breweries are only placed in a node i if dist[i]>maxd[i] and maxd[i]<the length of the road between i and i's parent. Special attention needs to be paid to using 64-bit integers for the cost and to using a non-recursive traversal of the tree (because of stack overflow).


Problem C: Chessboard

The time complexity for each test case is O(N^2). For each element (i,j) of the matrix, 3 values are computed: left[i,j] = the maximum number of colour-alternating squares to the left of (i, j) (inclusive), up[i,j] = the maximum number of colour-alternating squares starting from (i, j) (inclusive) and moving upwards and cmax[i,j] = the maximum size of a chessboard whose lower-right corner is at coordinates (i,j). cmax[i,j] is computed using left[i,j], up[i,j] and cmax[i-1,j-1]. Because the values for line i are only based on values from lines i and i-1 (the values for lines 1..i-2 not being necessary anymore), the program may use only 1 array for each of the values left and up and 2 arrays for the value cmax.


Problem D: Delay Constrained Maximum Capacity Path

Use binary search to look for the maximum capacity C. Then keep only those edges of the graph whose capacity is >= C and use a shortest path algorithm (Dijksta with heaps) to compute the length L of the shortest path from 1 to N. If L <= maximum time allowed, then try a larger capacity C ; otherwise, try a smaller one.


Problem E: Equations

There are several cases which need to be considered, depending on the values of a, b, c and delta=b^2-4*a*c.


Problem F: Find the Shortest Common Superstring

The shortest common superstring of 2 strings S1 and S2 contains the two strings in the order S1S2 or in the order S2S1 (the apparitions may overlap). All that needs to be done is to find out the length of the longest prefix of a string which is also a suffix of the other. This can be solved in linear time using the KMP algorithm.


Problem G: Gorilla.bas

The angle minimizing the speed is u=45 degrees (pi/4). For each building i, the angle ui at which the banana is thrown in order to reach its destination and touch the top of building i is computed. Let umax = max(ui). If umax <= 45 degrees, then 45 degrees is the answer (the speed depends only on the angle u, the gravitaional acceleration g, and the distance d); otherwise, the banana will be thrown at the angle umax.


Problem H: Horizontal and Vertical Rays

Sort the horizontal and vertical rays from the largest Y-coodinate to the smallest. For each horizontal ray, in the sorted order, choose the vertical ray which is above it and placed farther to the right. Ignore all the horizontal rays which are touched by the already chosen vertical rays. The time complexity is O((H+V)*log(H+V)).


Problem I: Intermediate Rounds for Multicasting

For each node i of the tree, compute the values cmin[i][p][q] = the minimum cost of the part of layer p which is below (or at the same level as) node i and contains q nodes from the subtree of node i. Layer p consists of the nodes which received the message in round p (the root is located on layer 0). cmin[i][p][q] can be computed based on the values calculated for the sons of i, using a knapsack-like dynamic programming algorithm. The time complexity is O(N^3 * K).


Problem J: Jimmy's Assignment

In every graph having the given properties there is a perfect matching (containing N/2 edges and all the N vertices). This has been proven by Petersen using the Tutte-Berge formula. The problem now becomes: Given the even number N and 3*N/2 useless pairs of numbers, print the number N/2 :)