Wednesday, March 2, 2005 Match summary The submissions came fast and furious in both divisions; more than 85 submissions were recorded in the first five minutes of the match. The rest of the submissions followed quickly, with a very large number of level three submissions in both divisions. The Division 1 leader at the end of coding phase, bmerry, saw his medium go down on on a challenge; the Division 2 leader, hhen926, lost his difficult to a challenge. Going into system tests, Division 1 was led by nicka81, haha, and John Dethridge; Division 2 was led by supernova, rsasanka, and sandeep. System tests left the top three in each division unchanged. At the end of the contest, it appeared this would be the first challenge since SRM 55 that every submission on the easy problem in Divison 1 passed. This was not to be, as haha, in an admirable feat of honesty, turned himself in on a violation of the unused code rule. This gesture may have cost him one hundred rating points, but this writer believes he'll get them back quickly enough. In his (or her) second match, marijnk, gained an astonishing 354 ratings points this match in Division 1. The ProblemsJustifyTextUsed as: Division Two  Level One:
A loop to find the longest string, followed by another that extended each string to this length, sufficed. Another approach lead to an elegantly short, although somewhat slower, solution: for (int i=0; i<text.length; i++) for (int j=0; j<text.length; j++) while (text[i].length() < text[j].length()) text[i] = " " + text[i] ;PipeCuts Used as: Division Two  Level Two: Used as: Division One  Level One:
Since there were few combinations of cuts, a simple enumeration followed by a test was sufficient. Sorting the cut array first provided some brevity: Arrays.sort(weldLocations) ; double sum = 0, tests = 0 ; for (int i=0; i<weldLocations.length) for (int j=0; j<weldLocations.length) { tests++ ; if (weldLocations[i] > L  weldLocations[j]  weldLocations[i] > L  100  weldLocations[j] > L) sum++ ; } return sum / tests ;AutoMarket Used as: Division Two  Level Three:
This problem is longest increasing subsequence on a partial ordering. A first approach might be to use recursion: int lengthFromHere(int carIndex) { int result = 1 ; for (int i=0; i<i++) if (ordered(i, carIndex)) result = Math.max(result, 1 + lengthFromHere(i)) ; return result ; } with a similar loop in the main program to find the best car for the head of the list. This doesn't run fast enough because of repeated computations, but memoization saves the day. Since the only argument to the recursive function is carIndex, dynamic programming also works, but first we need to order the cars in an appropriate way. (This is one advantage of memoization over dynamic programming; with memoization you don't need to consider how to order the state space.) Sorting by any particular attribute was sufficient, because the end result must be sorted by all attributes. Since the input was provided in arrays, we may want to sort it ourselves using bubblesort, rather than building all sorts of data structures. A dynamic programming iteration of the state space completes the solution; we do not include the head car in our result array just to save us the trouble of initializing the array: ... bubble sort arrays by cost attribute ... int res[] = new int[n] ; int returnValue = 0 ; for (int i=0; i<n; i++) for (int j=0; j<i; j++) if (ordered(j, i)) returnValue = Math.max(returnValue, res[i] = Math.max(res[i], 1+res[j])) ; return returnValue + 1 ;SmartWordToy Used as: Division One  Level Two:
With 26^4 or less than half a million states, and only eight transitions out of each state, a breadthfirst search works just fine. Each state could be encoded with a base26 integer, but using base 32 instead allows us to use shifts rather than divisions for some speedup. Encoding our state with an integer allows us to use a simple array for our distance map, although a fourdimensional array works also: int dist[] = new int[1+encode('zzzz')] ; int queue[] = new int[1+encode('zzzz')] ; We use two magic values in our distance array: 0 means we haven't gotten here yet, and 10 means it's an illegal square. Using 0 as the initial value means we don't have to initialize the array, but it also means we store one more than the actual distance. First we iterate through the forbid array, marking all the illegal places. Because of the 50 character limit for each element, this should run in time, but it's something to watch out for. Our breadth firstsearch then looks like: int queuePut = 0, queueGet = 0 ; queue[queuePut++] = encode(from) ; dist[encode(from)] = 1 ; int target = encode(to) ; while (queueGet < queuePut) { int pos = queue[queueGet++] ; if (pos == to) return dist[pos]  1 ; for (delta=1; delta<=1; delta += 2) for (i=0; i<4; i++) { int npos = ...calc next position... if (dist[npos] == 1) { dist[npos] = dist[pos] + 1 ; queue[queuePut++] = npos ; } } } return 1 ; As an exercise for the reader, what is the greatest possible return value of this function, over all legal inputs? DiskCutUsed as: Division One  Level Three:
A surprisingly large number of coders recognized this problem as classic Huffman coding. To solve this, you reconstruct the cuts in reverse order; the last cut for any given input set always involves the smallest two pieces. We can show this works by induction on a tree of cuts. An interior node represents a piece to be cut, and the children are the result of the cut; the leaf nodes are the final pieces. The total cost of any tree is the sum over all leaves of the area of the leaf multiplied by the distance from that leaf to the root. We prove, by induction, that any cut tree with minimum cost has the two smallest leaves adjacent and at maximum distance from the root. The base case is two pieces and a single cut for which only one tree is possible. For the inductive case, if the smallest values are not located as a pair of leaves at the maximum distance from the root, we can clearly swap them with the ones that are in that location and reduce the overall cost of the tree. The shortest solution is probably something like: int siz = percent.length ; int totalCost = 0 ; while (siz > 1) { Arrays.sort(percent, 0, siz) ; totalCost += (percent[0] += percent[1]) ; percent[1] = percent[siz1] ; } return (totalCost + 100) * (double)area ; A heap could also be used, or even just a simple linear search for the smallest values. An exercise for the reader is to solve this problem using a single simple array, in place, in linear time after the sort. A completely different approach was used by some coders, such as Andrew_Lazarev, who used a memoized recursive algorithm to build an optimal ordered binary search tree. (Others used dynamic programming; there is a strong relationship between memoized recursive algorithms and dynamic programming solutions.) If the leaves are ordered by frequency, any optimal ordered binary search tree is also an optimal Huffman tree. 
