Get Time
statistics_w  Match Editorial
SRM 233
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 Problems

JustifyText discuss it
Used as: Division Two - Level One:
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] ;
PipeCuts discuss it
Used as: Division Two - Level Two:
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)
Used as: Division One - Level One:
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 ;
AutoMarket discuss it
Used as: Division Two - Level Three:
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 ;
SmartWordToy discuss it
Used as: Division One - Level Two:
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?

DiskCut discuss it
Used as: Division One - Level Three:
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.

By radeye
TopCoder Member