JOIN
 Match Editorials
TCHS SRM 37
Tuesday, August 7, 2007

## Match summary

The TCHS SRM 37 attracted 75 coders, 17 of them newcomers. Due to system problems, the challenge phase was nullified, so only the coding and system test phases decided the results. Submission rates were pretty high and there were 24 coders who submited all three problems, and many of these were done in half the available time. It was the third problem that defined the match winners. A lot of hards went down during system tests -- at the end, only 6 coders remained who had all three solutions. Zhomart won the match. Close behind was neal_wu followed by davidsun.

# The Problems

BestHotel
Used as: Division One - Level One:
 Value 250 Submission Rate 57 / 64 (89.06%) Success Rate 43 / 57 (75.44%) High Score gstsclq for 248.33 points (2 mins 20 secs) Average Score 210.07 (for 43 correct submissions)

The one task that is needed to do is implement a function to determine whether an x-th hotel is disadvantageous or not. It can be done straightforwardly by following the definition from the problem statement.

```public boolean isDisadvantageous(int x){
for(int y = 0; y < n; y++)
if (price[x] >= price[y] && quality[x] <= quality[y])
if (price[x] > price[y] || quality[x] < quality[y])
return true;
return false;
}```

Clearly, we'll get the result for our problem by calling this function for each hotel. The time complexity of this solution is O(n2), where n is the number of hotels. Here, the constraints were low enough so the time complexity doesn't matter. Notice, though, that this problem can be also solved in O(n * log n) as well.

BooksNumbering
Used as: Division One - Level Two:

 Value 500 Submission Rate 45 / 64 (70.31%) Success Rate 42 / 45 (93.33%) High Score miroslavb for 484.33 points (5 mins 8 secs) Average Score 362.79 (for 42 correct submissions)

Denote b as the number of books in the library. The naive soluion would be based on a linear search of the value b. Due to the constraints from the problem's statement, such a solution may be not fast enough. There are two general methods that can be used to improve such a linear search. The first is to use binary search for the value b. In this case, the only thing we need to do is implement a function to determine the number of used digits in the labeling 1,2,...,b. The second method, which was chosen by a majority of coders, uses sequentional search for the number of digits of b. The total number of one-digit numbers is 9, of two-digit numbers is 90, of three-digit numbers is 900, etc. This counting will be stopped when the total number of digits is enough. See miroslavb's fastest solution for a clear implementation of this.

SumoTournament
Used as: Division One - Level Three:
 Value 1000 Submission Rate 25 / 64 (39.06%) Success Rate 6 / 25 (24.00%) High Score neal_wu for 791.58 points (15 mins 27 secs) Average Score 617.66 (for 6 correct submissions)

Let n denote the number of wrestlers. Clearly, the total number of all registrations is 2n, because each wrestler can be registered in or not. Any of these registrations (maybe all of them) can satisfy the constraint about average weight. Due to the time limit, a solution cannot be based on checking all registrations.

First, the idea of sorting weights in non-decreasing order seems to be useful for a start. To make our solution fast enough we need to use dynamic programming. Let A[i][j][w] be true if, out of the first i wrestlers you can select j of them with a total sum of weight w. It is now obvious that A[i][j][w] = A[i-1][j][w] OR A[i-1][j-1][w-weighti-1]. Moreover, if the second theorem is satisfied, the i-th wrestler can be used, and will be the weightiest. This idea will bring us a solution with a time complexity O(maxWeight * n3), which is close to the time limit.

A trick to improve it is based on a different use of the average weight. Let's subtract the value of averageWeight from each item of weight. For instance, from weights {80,90,100,110} and averageWeight=95 we obtain values {-15,-5,+5,+15}. Clearly, a zero sum of any such subtracted values represents a selection of wrestlers with the target average weight. So, the last task is to balance a zero weight from such modified values by using as big a weight as possible. According to this, we can erase the third index in the previous solution. Let B[i][w] be true if, out of first i values, we can balance the weight w. It is now obvious that B[i][w] = B[i-1][w] OR B[i-1][w-weighti-1]. Moreover, the i-th wrestler can be used in balancing as the weightiest if the value B[i][0] is also satisfied by the second term from the previous formula. This idea brings us a solution with a time complexity O(maxWeight * n2). The following code is an implementation of that.

```public int maxWeight(int[] weight, int averageWeight){

Arrays.sort(weight);
for(int i=0; i < weight.length; i++) weight[i] -= averageWeight;

final int MAX = 50*200*2 + 5;
boolean B[][] = new boolean[51][MAX];
final int ZERO = MAX/2;
Arrays.fill(B[0],false);
B[0][ZERO] = true;

int ret=-1;
for(int i = 1; i <= weight.length; i++)
for(int w = Math.max(0,weight[i-1]); w < Math.min(MAX,MAX+weight[i-1]); w++){
B[i][w] = B[i-1][w];
if (B[i-1][w-weight[i-1]]) {
B[i][w] = true;
if(w == ZERO) ret=Math.max(ret,weight[i-1] + averageWeight);
}
}
return ret;
}```
A lot of coders used an integer structure, where the values directly correspond to the answer - the maximal possible weight of any wrestler. Moreover, the space complexity in both solutions described above can be improved. See davidsun's solution for a clear implementation.

By Janq
TopCoder Member