Match Editorial

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 Problems

Value	250
Submission Rate	295 / 310 (95.16%)
Success Rate	278 / 295 (94.24%)
High Score	pankajbhamoriya for 249.85 points (0 mins 41 secs)
Average Score	217.11 (for 278 correct submissions)

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] ;

Value	500
Submission Rate	238 / 310 (76.77%)
Success Rate	188 / 238 (78.99%)
High Score	supernova for 491.16 points (3 mins 49 secs)
Average Score	352.12 (for 188 correct submissions)

Value	250
Submission Rate	144 / 145 (99.31%)
Success Rate	143 / 144 (99.31%)
High Score	wleite for 247.65 points (2 mins 46 secs)
Average Score	226.34 (for 143 correct submissions)

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 ;

Value	1000
Submission Rate	101 / 310 (32.58%)
Success Rate	32 / 101 (31.68%)
High Score	Crystal for 868.57 points (11 mins 24 secs)
Average Score	686.24 (for 32 correct submissions)

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 ;

Value	500
Submission Rate	83 / 145 (57.24%)
Success Rate	63 / 83 (75.90%)
High Score	ploh for 420.22 points (12 mins 53 secs)
Average Score	289.18 (for 63 correct submissions)

With 26^4 or less than half a million states, and only eight transitions out of each state, a breadth-first search works just fine. Each state could be encoded with a base-26 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 four-dimensional 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 first-search 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?

Value	1000
Submission Rate	47 / 145 (32.41%)
Success Rate	27 / 47 (57.45%)
High Score	Abednego for 914.30 points (8 mins 52 secs)
Average Score	706.52 (for 27 correct submissions)

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[siz-1] ;
}
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.