Qualification Round 1 September 7, 2006 Match summaryThanks to the new qualification system, a lot of nonred coders got a perfect opportunity to win a TopCoder round. Newcomer MenShoiKin used this opportunity, getting 5 successful challenges on the way to the round win. Iceman was less than 3 points behind, and and elhipercubo rounded the top 3. Unfortunately, nobody was able to correctly solve the hard problem. Due to low participation level, the round cutoff was lower than 180 points, allowing a lot of lowerrated coders to qualify. The ProblemsMedianProcessUsed as: Division One  Level One:
In this problem you need only to carefully implement the algorithm described in the statement. The easiest way to compute the median is described in notes  sort the numbers and take the element with the proper index. C++ code follows: int getScore(vectorStudentsOrdering Used as: Division One  Level Two:
To solve this problem we need to make a couple of observations. First, if in the final arrangement we separate boys and girls, both boys' (and girls') heights will go in the nondescending order. Second, if several boys (or gilrs) are of the same height, their names will go in the alphabetical order. These two observations are the key to the algorithm. Order boys and girls independently by height (splitting ties by names). Let the sorted arrays look like B1, B2, ..., BN and G1, G2, ..., GM respectively. Then the optimal ordering can be either B1, G1, B2, G2,... or G1, B1, G2, B2, ... Of course, each of these orders must satisfy several requirements. Heights in the order must go in the nondescending order. Also, if, for example, the line starts from a boy, the total number of boys cannot be smaller than the total number of girls and cannot exceed the number of girls by more than 1. To find the answer, we build both ordering described earlier and compare their results. C++ implementation of this algorithm follows: string findOrder(vectorPenPuzzle Used as: Division One  Level Three:
This problem, as many other puzzle problems, is a modified shortest path problem. To build the graph, we represent each state of the puzzle (i.e.  colors of plates on all sides) as a node, and each valid modification as an edge between two nodes. Removing any of the plates from the initial puzzle gives us several starting points, and all solved puzzles are our destinations. To find the shortest path we use the BFS algorithm with a queue (see this tutorial to read more about shortest paths). To avoid visiting the same state more than once, we save all visited states in a map. The hard part of the problem is to make this solution run in time. Here I describe several tricks, which may be useful to you in the future. The first (and wideused) trick is to create a hash value for each state, to make comparing two states faster. Since the puzzle can not contain more than 12 plates of 5 different colors (4 colors + 1 extra "color" to mark an empty slot), the state of the puzzle can be represented as a 64bit number (6 ^ 12 is ~ 2.2 * 10^{9}). Since this optimization is not enough, we will to reduce the search space to avoid checking the same state twice. Reducing the space includes introducing the normal form for each state, so different states will be represented by the same node. First, the puzzle is symmetrical to rotations. That is, if we rotate each level of the puzzle, the resulting puzzle will have the same solution as the initial one. Since each side of the puzzle can be taken as "the first" side, each unique state of the puzzle may be represented as several nodes in our graph (for example, nodes {"ABC", "AC_"}, {"BCA", "C_A"} and {"CAB", "_AC"} represent the same unique state of the puzzle). To avoid this, we need to select the first side unambiguously. The most natural way of doing this (at least for me) was selecting the side with the empty slot as the first side. In this case, the normal state of the puzzle is {"DABA", "CB_C"} will be {"BADA", "_CCB"}. Another optimization uses the fact that the puzzle is symmetrical in respect to colors  so, if we'll make all green plates blue, and all blue plates green, the solution to the puzzle will remain the same (for example, solutions to puzzles {"ABC", "AC_"} and {"BAC", "BC_"} are equal). Representing these as one node can be made in the following way. Iterate through all plates of the puzzle in some fixed order, indexing all colors in the order you meet them. Then, change the color of each plate to the index of its color. For example, if the puzzle is {"DABA", "_CBC"} (or {"DBAB", "_CAC"}), and we iterate from the top level to the bottom, from the first side to the last, the normal state of the puzzle will be {"1232", "_434"}, or, using letters, {"ABCB", "_DCD"}. To see the complete solution of this problem, check ACRush's solution in practice room. 
