Online Round 1 Saturday, February 16, 2008 Match summaryThis Saturday more than 1,500 coders logged into the arena to compete in the first round of this year's TCO. With 900 places for advancers, the strategy to advance was clear: slow and steady. In the end, the number of coders with positive scores was a bit lower than 900, and thus everyone with a positive score advanced to the next round. Of course, not every participant decided to go for the slow and steady approach. Some of the higherrated coders went for fast and steady :) A bug in the room seeding algorithm forced the admins to prepare a fix during the coding phase, and then fix everything during the intermission. This was kind of like watching a Formula 1 in the pit stop: in a short amount of time, many things had to happen to allow the competition to proceed. Luckily, everything went smoothly, and the only effect the coders could see was that the intermission was 10 minutes longer. Of course, that was not necessarily a bad thing. While many coders spent part of the time chatting, some were glad to have ten more minutes to prepare challenge cases for greedy solutions of the 250, and incorrect or slow solutions of the 500 and 1000. The round went to Petr after his spectacular performance in the challenge phase. His 11 correct challenges (and not a single wrong one) gave him an almost 550 point lead before the rest of the coders. Second place went to SkidanovAlex. Looking at his rating graph, soon we'll have a new target. Another TopCoder veteran, tomek, finished third, even with a resubmitted easy problem. The ProblemsDiscountCombinationUsed as: Division One  Level One:
There are up to 2^{50} possible ways to buy the shoes we don't want. In two seconds it is not possible to try all these ways to find the best one. We have to find something that will help us prune the search. One such observation: Suppose that we have two shoe models that give us the same discount. Clearly, we should prefer the cheaper of these two. The other observation we need is that the problem statement promised us that there are only three types of discounts. What can we do now? Take all the models, and split them into three heaps, one for each discount type. Now, within each heap we can order the models according to their price. What did we gain? Suppose that the optimal solution involves buying A models from the first heap, B models from the second heap, and C models from the thid heap. We now know that those must be the A (or B or C) cheapest models from that heap. All that remains is to find the right values A, B, and C that give us the best total price. Each of these values is at most 50, and thus we can simply examine all triples (A,B,C) and pick the best one. C++ code follows. double minimumPrice(vector <string> discounts, int price) { vector<int> disc[4]; int N = discounts.size(); for (int i=0; i<N; i++) { int x,y; stringstream(discounts[i]) >> x >> y; disc[y].push_back(x); } for (int i=1; i<=3; i++) sort(disc[i].begin(), disc[i].end()); double res = 1e30; for (unsigned a=0; a<=disc[1].size(); a++) for (unsigned b=0; b<=disc[2].size(); b++) for (unsigned c=0; c<=disc[3].size(); c++) { double now = 0.0; for (int i=0; i<a; i++) now += disc[1][i]; for (int i=0; i<b; i++) now += disc[2][i]; for (int i=0; i<c; i++) now += disc[3][i]; now += price * pow(0.99,a*1.) * pow(0.98,b*1.) * pow(0.97,c*1.); res = min(res,now); } return res; }Chomp Used as: Division One  Level Two:
We can easily find out that after each move the game board will have the following shape: XXXXXXXX XXXXXXXXXXXXX XXXXXXXXXXXXXXXX More precisely, the state of the game can be described by three integers A ≤ B ≤ C, giving the length of the top, middle, and bottom row, respectively. Note that C≤100, thus there are roughly 10^{6} states. In each state, the number of possible moves is equal to the number of remaining cells. It follows that the number of possible moves is never greater than 300. (Exact values: There are 176,851 valid positions, and we have to examine a total of 26,527,650 moves.) This makes it possible to search the entire state space, and for each state (i.e., position of the game) compute which player wins. The algorithm for this is described in rasto6sk's tutorial on games. This algorithm uses the following idea: A position is winning (for the player to move), if there is a move that leads to a position that is losing (again, for the player to move, which would be our opponent). And vice versa, a position is losing if all moves lead to winning positions. This algorithm can be easily extended to compute the number of moves: If we are in a winning position, and there are multiple losing positions to choose from, pick the one where the game will be shortest. And if we are in a losing position, do the contrary. The solution is most easily implemented using recursion with memoization. C++ code follows. int memo[105][105][105]; int solve(int a, int b, int c) { // base case: I'm forced to lose if (a==1 && b==0 && c==0) return 1; // memoization: if I already computed this, return the result int &result = memo[a][b][c]; if (result != 0) return result; result = 1; int r[3]; r[0]=a; r[1]=b; r[2]=c; // try all possible moves for (int row=0; row<3; row++) for (int col=0; col<r[row]; col++) { if (row+col==0) continue; // ... except for the move where we lose int s[3]; s[0]=a; s[1]=b; s[2]=c; for (int i=row; i<3; i++) s[i] = min(s[i], col); // now, s[] contains the row lengths after the move int curr = solve(s[0],s[1],s[2]); if (curr < 0) { if (result<0) result=1curr; // we found the first winning move else result=min(result,1curr); // check whether this winning move is better } else { if (result<0) result=min(result,curr1); // check whether this losing move is better } } return result; } int moves(int N) { return solve(N,N,N); }BoxFilling Used as: Division One  Level Three:
The process described in the problem statement can be visualised as "peeling off" layers from the box. First, we remove the "top" layer, then the "back" layer, then the "left" layer, then the "top" layer again, and so on, until the entire box is removed. A similar process is used for the 2D case: alternately we remove the "top" and the "left" row of the rectangle. Of course, the 2D rectangles can have different orientations in 3D space, and this is where those phrases like "all cubes with minimal X and Y coordinates" came into play – they simply made sure that for any orientation the process will work in the same way. Of course, we can't afford to number each and every unit cube in the box, there are too many of them. Lucky news is that we don't need to do this, and it will even make our solution a bit simpler. Most of the instructions are "take this set of cubes that doesn't contain the one you need, and number it". At this point, the only thing that matters is the volume of that set (i.e., the count of unit cubes it contains). If the last value used before this set was N, and this set contains M cubes, then the last of them will get the number N+M. And we don't really care how the numbers N+1 to N+M are distributed. This allows us to write a simple function that solves the 3D case: Remove 2D rectangles of cubes and sum their sizes, until we find the layer that contains our cube. // c* is in [0,s*) long long solve3D(long long sx, long long sy, long long sz, long long cx, long long cy, long long cz) { long long result = 0; while (true) { // remove the top layer if (sx==1  sy==1  sz==1) break; if (cz==0) return result + solve2D(sx,sy,cx,cy); result += sx*sy; cz; sz; // remove the back layer if (sx==1  sy==1  sz==1) break; if (cy==0) return result + solve2D(sx,sz,cx,cz); result += sx*sz; cy; sy; // remove the left layer if (sx==1  sy==1  sz==1) break; if (cx==0) return result + solve2D(sy,sz,cy,cz); result += sy*sz; cx; sx; } // if we got here, a single 2D case remains of the entire box if (sx==1) return result+solve2D(sy,sz,cy,cz); if (sy==1) return result+solve2D(sx,sz,cx,cz); if (sz==1) return result+solve2D(sx,sy,cx,cy); } As the volume is at most 10^{18}, one of the dimensions is at most 10^{6}, and thus the whileloop will make at most 10^{6} iterations. We can make a similar solution for the 2D case. However, there is one small catch: Removing rows one at a time can lead to exceeding the time limit for a (10^{9} x 10^{9} x 1) box. Luckily, we can easily speed this solution up. If our cube has 0based coordinates (CX,CY), then we will clearly make free=min(CX,CY) full iterations of the whileloop before hitting our cube. We can easily count all the cubes used in these steps, and only then do the remaining part of the function. XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXX.......?.... XXX............ XXX............ XXX............ The schema above shows a 15x7 rectangle after three iterations. The cells denoted 'X' are those that were numbered already, '?' is our cube, its coordinates are (10,3). The count of 'X'es is (15*3) + (73)*3. The general 2D solution will look as follows: // c* is in [0,s*) long long solve2D(long long sx, long long sy, long long cx, long long cy) { long long result = 0; long long free = min(cx,cy); result += free*(sx+syfree); cx=free; cy=free; sx=free; sy=free; while (true) { if (sx==1  sy==1) break; if (cy==0) return result+cx+1; result+=sx; cy; sy; if (cx==0) return result+cy+1; result+=sy; cx; sx; } if (sx==1) return result+cy+1; else return result+cx+1; } And our work is done. All that remains is to count the number of dimensions of the given box, and then to call the appropriate function: long long getNumber(int sx, int sy, int sz, int cx, int cy, int cz) { cx; cy; cz; if (sx==1 && sy==1) return cz+1; if (sx==1 && sz==1) return cy+1; if (sy==1 && sz==1) return cx+1; if (sx==1) return solve2D(sy,sz,cy,cz); if (sy==1) return solve2D(sx,sz,cx,cz); if (sz==1) return solve2D(sx,sy,cx,cy); return solve3D(sx,sy,sz,cx,cy,cz); } 
