Tuesday, August 30, 2005 Match summary Division 1 was faced with a pretty standard problemset, with the medium problem slightly harder than average. JongMan was between the first coders to submit all three problems. Sadly, later he found a bug in his 250 and the resubmit costed him the SRM win and moved him to the fifth place. After the coding phase the field was lead by kalinov and Toivoa. But the match was far from being over. We saw quite a lot of challenges for all three problems, especially for the easy one. After the dust settled, Toivoa was left fourth, Zuza claimed the third place with the help of 5 successful challenges, kalinov finished second... ...and the SRM win goes to marek.cygan. Congratulations! In division 2 the hard problem was pretty tricky, thus only two solutions made it through the system test phase. The only coder to have all three problems passed was zmast3r – and he won division 2 by a fair margin. phoenixinter and a newcomer endrjo finished second and third. Another newcomer LemonTree had the other successful solution for the hard problem, but his failed medium placed him only in the fifth place. The ProblemsSpreadsheetColumnUsed as: Division Two  Level One:
This problem was pretty simple. To avoid any confusion, probably the best way is to handle the two cases separately. As long as you tested your solution on all examples, you should've been on the safe side. string result; if (column <= 26) result += char('A'+column1); else { column = 27; result += char('A' + (column/26)); result += char('A' + (column%26)); }PrimeStatistics Used as: Division Two  Level Two: Used as: Division One  Level One:
The first step to solve this problem is (of course) being able to say whether a given number is prime. Either you could precompute this using the sieve of Erathostenes, or you could write a simple function that checks whether a number is prime. How to do this? If a number N is not prime, it has a nontrivial divisor. Let D be the smallest of them. Clearly D≥2. The number N/D is also a nontrivial divisor of N. But D is the smallest one, therefore D≤N/D. In other words, D*D≤N. A simple way of primality testing follows: boolean isPrime(int N){ if (N<2) return false; for(int i = 2; i*i <= N; i++){ if(N%i == 0) return false; } return true; } The time complexity of this function is clearly O(sqrt(N)). Note that the upper bound for the cycle is often written as "i ≤ sqrt(N)", but our way is a bit faster and we avoid using real numbers. Now all you had to do was to loop through the given interval, for each number check whether it is prime and for each prime compute its remainder. There were lots of successful challenges for this problem. The problem with most of the flawed solutions is that they considered 1 to be prime. Note that 1 is never considered to be a prime number. This was also clearly stated in the problem statement... but avoided in the examples. Many coders spotted this and were awarded in the challenge phase. GomokuBoardCheckerUsed as: Division Two  Level Three:
Algorithmically there's nothing that difficult in this problem. But there were many cases to consider... and not all of them were covered by the examples. This made the problem pretty tricky, with only two solutions handling all the cases correctly. Clearly, we need a systematic way of approaching the problem. First of all, let's count the number of 'O's and the number of 'X's on the board. If these counts differ by more than 1, the position is illegal. If they differ by 1, we know, who made the last move. If they are equal, either player could make the last move. Now we check whether each player has got a 5inarow. The easiest way: Loop through all squares, loop through all 8 directions and check, whether there's a 5inarow starting on the chosen square and going in the chosen direction. // constants for the 8 directions int dr[] = { 1, 1, 1, 0, 0, 1, 1, 1 }; int dc[] = { 1, 0, 1, 1, 1, 1, 0, 1 }; // the number of rows and columns int R, C; boolean inside(int x, int y) { return (x>=0 && x<R && y>=0 && y<C); } boolean hasFive (char who, vector<string> board) { for (int r=0; r<R; r++) for (int c=0; c<C; c++) for (int d=0; d<8; d++) if (inside( r+4*dr[d] , c+4*dc[d] )) { boolean ok=true; for (int k=0; k<5; k++) if (board [ r+k*dr[d] ][ c+k*dc[d] ] != who) { ok=false; break; } if (ok) return true; } return false; } If both players have got a 5inarow, the position is invalid. If nobody has 5inarow, the position is either a game in progress, or a draw. To distinguish between these two cases, we simply check whether the board is full. We are left with the case that exactly one player has got some 5inarows. If she couldn't make the last move, the position is invalid. If she could, she had to make all of them in her last move. (The game has to end immediately after one of the players won.) The easiest way to check whether this is possible is brute force: For each square with her symbol try whether this could be the last move (i.e., check whether the board with this symbol removed contains any 5inarows). If no possible last move is found, the position is invalid, otherwise the player won. EncodingTreesUsed as: Division One  Level Two:
In the whole text, the abbreviation BST means "a binary search tree with N nodes labeled from 0 to (N1)". (In the problem statement the nodes were labeled by lowercase letters, but dealing with numbers will simplify this text a little bit. Converting numbers to letters is trivial.) Also, we will assume that the trees are indexed from 0. Counting all BSTs with N nodes is a pretty standard combinatorial tasks. Let C(N) be the count of BSTs with N nodes, let C(N,K) be the count of BSTs with N nodes with the label K in the root node. How to compute C(N,K)? The left subtree contains K nodes (labeled from 0 to K1) and the right one contains N1K nodes (labeled from K+1 to N1). The left subtree is again a BST, thus there are C(K) possible left subtrees. If we subtract (K+1) from each label in the right subtree, we get another BST  and vice versa, from each BST on N1K nodes we can create a possible right subtree by adding (K+1) to each label. Thus there are C(N1K) possible right subtrees. Clearly, each pair (left subtree, right subtree) corresponds to one BST. We get the equation: C(N,K) = C(K) * C(N1K) and we may compute the total count of BSTs with N nodes by summing through all possible labels of the root node: C(N) = sum(K=0; K<N; K++) C(K) * C(N1K) (As a side note, the numbers C(N) are known under the name Catalan numbers and they can be found in many different places of combinatorics.) After computing all the numbers C(N,K) the reconstruction of a tree from its index is straightforward. In fact, the approach we use is the most common way of solving such combinatorial tasks. First, we need to determine the label of the root node (which is also the first label in the preorder code of the tree). This can be done by counting the trees with the root node having the label 0, 1, etc.: The trees with indices from 0 to C(N,0)1 have the label 0, trees from C(N,0) to C(N,0)+C(N,1)1 have the label 1, etc. Now we have the label K of the root node. Moreover, we can easily determine a new index I of our tree between these C(N,K) trees. Now all we have to realize is that these trees are ordered by the preorder codes of their left subtrees and only in case of equality by the preorder codes of the right subtrees. In other words: We know that there are C(K) possible left subtrees and C(N1K) possible right subtrees. Given our index I, the left subtree we seek has the index I / C(N1K) and the right subtree has the index I % C(N1K). Thus we can compute their codes recursively using the same approach. Note that the right subtree doesn't use label 0..NK2, thus we need to shift the computed preorder code by K+1. The value we return is: (label in the root node) + (preorder code of the left subtree) + (appropriately shifted preorder code of the right subtree). String getCode(int N, int index) { if (index >= C[N]) return ""; int seen = 0; for (int rootLabel=0; rootLabel<N; rootLabel++) { seen += C[rootLabel] * C[N1rootLabel]; if (seen > index) { // enough trees found, rootLabel is correct seen = C[rootLabel] * C[N1rootLabel]; int newIndex = index  seen; int leftIndex = newIndex / C[N1rootLabel]; int rightIndex = newIndex % C[N1rootLabel]; String result1 = getCode(rootLabel, leftIndex); String almostResult2 = getCode(N1rootLabel, rightIndex); String result2 = ""; for (int i=0; i<almostResult2.length(); i++) result2 = result2 + ( (char)(rootLabel+1+(int)res2.charAt(i)) ); return (char)(rootLabel + 97) + result1 + result2; } } }StackingBoxes Used as: Division One  Level Three:
When trying to solve this problem greedily, there are many simple and wrong approaches. Putting the box with the largest carrying capacity on the bottom doesn't work. And neither does putting the heaviest box on the bottom. Many of the coders went for a greedy solution... and failed. But still, the intuition behind these approaches is not that faulty. Suppose that we finished building a valid stack of boxes. Let B be any box in the stack and let A be the box immediately above B. From now on, consider only the stack formed by the box B and all boxes above it. The total weight of this stack is at most w_B + c_B. Now suppose that w_A + c_A > w_B + c_B. This means that c_A > (w_B + c_B)  w_A ≥ (weight of all the boxes)  w_A. In other words, the box A is able to carry all the other boxes in our stack. Thus by swapping A and B we obtain a new valid stack with the same number of boxes. (We should note that B is carrying less than before and nothing has changed for the other boxes, thus the stack is valid indeed.) As a consequence, we may rearrange each valid stack of boxes in such a way that the boxes are ordered according to the sum of their weight and carrying capacity. Thus we only have to search for an optimal stack, where the boxes appear in this order. This can be done using a simple dynamic programming approach: Process the boxes in increasing order of their sum. For each stack size, keep the smallest weight of a valid sorted stack created from the currently processed boxes. // assumptions: // W[i] is the weight of the ith box // C[i] is its carrying capacity // for all i, W[i] + C[i] <= W[i+1] + C[i+1] // in the beginning, the only valid stack is the empty one for (int i=0; i<=N; i++) best[i]=1000000047; best[0]=0; // the largest stack size so far is zero int maxCount=0; for (int i=0; i<N; i++) { // we now process the ith box for (int j=maxCount+1; j>0; j) { // let's try to make a stack with j boxes // with the current one on the bottom // for this to work, the currently smallest stack // of j1 boxes mustn't be too heavy if (C[i] >= best[j1] && best[j1]+W[i] < best[j]) { best[j]=best[j1]+W[i]; if (j>maxCount) maxCount=j; } } } 
