Match Editorials

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

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(n²), 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.

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.

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 2ⁿ, 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-weight_i-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 * n³), 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-weight_i-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 * n²). 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;
}