Tuesday, August 7, 2007 Match summaryThe 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 ProblemsBestHotelUsed as: Division One  Level One:
The one task that is needed to do is implement a function to determine whether an xth 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^{2}), 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. BooksNumberingUsed as: Division One  Level Two:
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 onedigit numbers is 9, of twodigit numbers is 90, of threedigit 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. SumoTournamentUsed as: Division One  Level Three:
Let n denote the number of wrestlers. Clearly, the total number of all registrations is 2^{n}, 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 nondecreasing 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[i1][j][w] OR A[i1][j1][wweight_{i1}]. Moreover, if the second theorem is satisfied, the ith wrestler can be used, and will be the weightiest. This idea will bring us a solution with a time complexity O(maxWeight * n^{3}), 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[i1][w] OR B[i1][wweight_{i1}]. Moreover, the ith 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^{2}). 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[i1]); w < Math.min(MAX,MAX+weight[i1]); w++){ B[i][w] = B[i1][w]; if (B[i1][wweight[i1]]) { B[i][w] = true; if(w == ZERO) ret=Math.max(ret,weight[i1] + 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.

