May 18, 2002 Match summary Single Round Match 89 offered a nice diversity of problems, ranging from some simple mathematics to digital picture processing techniques to some advanced graph theory. Thus there is much to be learned from this match. Division 1 coders faired rather poorly, most likely because of misleading point values and difficult problems. The Problems
Whenever using the / operator, keep in mind that it will be integer division if both of its operands are of integral types (even when assigning to a float or double. Thus, to force floating point division, cast at least one of the arguments to a floating point type. Another method was to observe that, since k > 2 must hold, the maximum value of b is sqrt(n). This gives an upper bound of 14142. For each b between 1 and 14142 inclusive, iterate through the powers k of b until b^{k} >= n. The first b, k that we find that satisfies b^{k} = n (if we iterate through values of b in ascending order) will be our answer. The most common problems were fencepost errors (upper bounds off by 1) and floating point instability (particularly the problem related to the first method described above). The Filter problem is equivalent to opening the input image with the following structuring element (with origin at the center):
The easiest method would be to simply implement the erosion and dilation operators for the structuring element above. Each could be implemented as a local operator  that is, a function that, given an image and a location in that image, returns a pixel value to be placed in the same location in a new image. The erosion and dilation operators are then: /* a representation of which pixels are turned on in our structuring element */ int[][] offsets = { { 0, 0 }, { 0, 1 }, { 0, 1 }, { 1, 0 }, { 1, 0 } }; /* pixels outside the image are off */ boolean get_pixel(boolean[][] image, int r, int c) { return r >= 0 && c >=0 && r < image.length && c < image[0].length && image[r][c]; } boolean erosion_operator(boolean[][] image, int r, int c) { for(int i = 0; i < offsets.length; i++) if(!get_pixel(image, r + offsets[i][0], c + offsets[i][1])) return false; return true; } boolean dilation_operator(boolean[][] image, int r, int c) { for(int i = 0; i < offsets.length; i++) if(get_pixel(image, r + offsets[i][0], c + offsets[i][1])) return true; return false; } In general solutions to this problem could be seen as some sort of variant of an opening. AlgorithmThe solution consists of performing a breadthfirst search. This consists of maintaining a frontier of all the possible locations the ball can be at after k strokes. Initially the ball is somewhere in the tee area. For each stroke, we generate a new frontier from the previous one. For each location in the frontier, we iterate through each club and each direction and compute the location the ball would be at if we struck it with that club in that direction. This new location then goes into the new frontier. If the new location is where the hole is, we return the number of strokes it took to get there. Since this is a breadthfirst search, the first solution we find will by definition be the one of minimum strokes.There are at most 5 clubs, and exactly six directions. Thus for each location in an old frontier we will generate at most ^{6n} new locations for n clubs. If there are x locations in the old frontier, we will obtain at most 6nx locations in the new frontier. Since the complexity of our solution is exponentially proportional to the size of the initial frontier, we want it to be 1. However, we are given as input an area about the origin in which the ball may start. If we were to use this entire area as the initial frontier, our solution would fail to finish in time (and would consume too much memory). The upper bound on teeSize is 10000, and 60000^{5} happens to be a very large number. The trick, instead, is to think of the effect of translating the ball to some location within the tee area from the origin. We can think of our solution as generating a set of paths (of length less than or equal to 5) through the hexagonal grid. Suppose we have a set of paths originating at the origin (that is, our BFS computed with the origin as the only element of the initial frontier). If we were to translate the ball along the east and southeast axes, the effect would be to translate each point in each path in the exact same manner. Therefore we can see that there is no point in adding all the points within the tee area to our initial frontier. Instead, all we have to do is translate our tee area so that it is centered at each location we reach, and see if the hole lies within the tee area. In other words, for each location we reach, instead of checking if it is the same location as the hole, we check if it is within a distance of teeArea from the hole. So, we begin with a frontier of size 1 and build at most 5 frontiers. Therefore, in the worstcase scenario, we will visit (6n)^{5} = 7776n^{5} locations. For n = 5, this is 7776 * 3125 = 2425000, meaning that this solution is tractable given its constraints. ImplementationThe only real difficulty in implementing the above algorithm is working with the hexagonal coordinate system. For representing locations, we will use the same method as that of representing the hole location: a coordinate pair (e, se) representing a distance of e travelled east followed by a distance se travelled southeast. Let the location of the hole be (e_{0}, se_{0}). We need a way of computing the minimum radius of a hexagon centered at (e_{0}, se_{0}) that contains (e, se). To do this, we first find (e', se') = (e, se)  (e_{0}, se_{0}). If e' and se' have the same sign, the minimum radius is e' + se'. Otherwise, the minimum radius is max(e', se'). If this minimum radius is less than or equal to teeArea, we have hit the hole.Most people in fact implemented a depthfirst search rather than a breadthfirst search, as it is easier to implement and requires much less memory. For this problem, a DFS is equivalent to an exhaustive BFS, so its runtime complexity is equivalent to that of the worstcase BFS. Since the DFS implementation requires no maintenance of a queue, it is obviously the fastest solution to implement. Since I was unable to solve this problem myself, I looked to the few submissions that passed the system tests to see how others approached the problem. There seemed to be two types of solutions: either a depthfirst search or a graph theoretic solution. DepthFirst SearchAlgorithmThe first step is to precompute the number of rowpairings one can get for any rowpairing configuration. A rowpairing configuration can be represented as a binary string, such as "1100" for a row of length 4. A 1 bit represents a child that is paired with someone in the same row, while a 0 bit represents either an adult or a child paired with someone in the same column. We mark as invalid configurations that do not describe a valid rowpairing (e.g. "1101" is invalid because the rightmost child is not actually paired with anyone); otherwise we count the number of pairs in the configuration (e.g. "1100", "0110", and "0011" each represent 1 pair, and "1111" represents two pairs.Now we can recursively generate all valid pairings in the square of kids, subject to the constraints of the problem. We do this by working from the bottom row up (or the top row down). For each row, we have a mask which consists of the locations occupied by adults or by children paired with children in the previous row. We then iterate through each valid rowpairing configuration. If the configuration does not contain any pairs that occupy the same locations as adults or children paired with someone in the previous row, then we generate a new mask and recursively move on to the next row. If we visit all the rows and end up with an empty mask, then we have a valid pairing for all the kids. We can count the number of rowpairs as we go along, and then remember the maximum value found when a valid pairing was reached. Thus our counting function looks something like: Keep in mind that x << y is equivalent to 2^{y}x.int numpairs[1 << n]; int adults[n]; int best = 1; void count(int row, int mask, int running_total) { if(row == 1) { if(mask == 0 && running_total > best) best = running_total; return; } for(int i = 0; i < (1 << n); i++) if(numpairs[i] != INVALID && fits(i, mask  adults[row])) count(row  1, (1 << n)  1  (i  mask  adults[row])); } count(n  1, 0, 0); return best; ImplementationYarin's solution is an excellent implementation of this algorithm, using bitwise operators to handle all the configuration representations and masks. There are 2^{n} rowpairing configurations (many of which are invalid). These can be represented as an array indexed by an integer whose binary representation is also that of the configuration. The values stored in the array are then the number of rowpairs in each configuration (or some special value to represent invalid configurations).The binary representation of an integer can also represent a parent mask or the mask derived from a previous row's configuration. If applying the bitwise and operation to a rowconfiguration and either of these masks results in a nonzero value, then that particular rowconfiguration does not fit the constraints. Otherwise the mask for the next row can be obtained by taking applying a bitwise or operation to the row configuration and the two masks and computing the complement of that value (i.e., ~(rowconfig  parentmask[row]  mask)). We add to our running sum the number of pairs defined by the row configuration, and recurse to the next row. If there is no next row, and our new mask is 0, we remember our sum of rowpairs if it is greater than the best value obtained so far. For further optimization, we need to employ memoization techniques for our recursive function. Since it takes as parameters 0 <= row < n and 0 <= mask < 2^{n}, we can create an array of dimension n x 2^{n} for remembering values. Graph TheoreticThe group of children can be represented as a graph, where each child is a vertex and there is an edge between each pair of adjacent children. It turns out that this graph is a bipartite graph. A bipartite graph consists of two sets of vertices (we will call them V_{1} and V_{2}), such that within each set there exists no adjacent vertices. If we were to place the children onto a chessboard, V_{1} would consist of children standing on white squares and V_{2} would consist of children standing on black squares.The definition of the problem gives that each child (vertex) should have at most one partner (edge) (to be valid, every child should have exactly one partner, but we will get to that shortly). In graph theoretic terms, this is what is known as a matching, which is a set of edges such that no vertex included more than once. It follows then that any pairing of children (even if incomplete) is a bipartite matching. A maximum bipartite matching is the matching of maximum cardinality of a bipartite graph. If the maximum bipartite matching gives (n^{2}  adults) / 2 edges, then there exists a way to pair up all of the children. Although simply finding a maximal bipartite matching is insufficient to solve this problem, it might be helpful to demonstrate how one might be found. The maximum bipartite matching problem can be reduced to the network flow problem. Then attach a source vertex to all of the vertices in V_{1} and a sink vertex to all of the vertices in V_{2}. Give each edge a capacity of 1. The FordFulkerson algorithm or some other flow maximization algorithm can then be employed to obtain a maximum flow. The edges utilized in the maximum flow then constitute the maximum matching. However, we cannot stop at simply obtaining a maximal bipartite matching. We need the matching that gives the most horizontal pairings. To obtain this, we must assign weights to edges in the bipartite graph. Unfortunately, once we do this, we can no longer use the network flow algorithm to solve the problem. For each edge that is horizontal (between children on the same row), we assign a weight of 1. Otherwise we assign a weight of 0. The weight of the bipartite matching with the maximum cumulative weight then gives us the answer. The solution we need for this particular problem is the solution to the maximum weighted bipartite matching problem, also known as the assignment problem. One algorithm that solves this problem is known as the KuhnMunkres algorithm (also described here). Member Comments Just wanted to comment that the SRM 89 Problem Set Analysis was fantastic! Very detailed, and a great analysis of the correct algorithms involved. Keep up the good work! 
