Tuesday, November 8, 2005 Match summary Division 1 saw a quite traditional match, with almost no challenge opportunities and a quite hard 1000 point problem only a few coders could get right. Apparrently, after the rules for the next TCO were announced, tomek found new motivation to do well in the SRMs and he won this one the way we remember him from the "old times" – with a solid time on all three tasks. Petr took second and pparys third. The only other coder to get the hard task right was ploh, but his failed medium placed him only fourth. In Division 2, wshtb had the fastest time on the hard problem and won the match, with olive in second, and X_X in the third place. The best newcomer was pytko.13, he placed fifth with the help of the fastest time on the medium problem. The ProblemsCheckFunctionUsed as: Division Two  Level One:
The best way to do problems like this one is to put all the constants from the problem statement into constants in your program. In this case, we will make a simple array that contains the number of dashes for each of the digits. Then for each digit in code we look into this array and add the corresponding value to the result. C++ code follows: // a zero has 6 dashes, a one has 2 dashes, ... int dashes[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; int newFunction(string code) { int result = 0; for (unsigned int i=0; i<code.size(); i++) result += dashes[ code[i]'0' ]; return result; }BlackWhitePlane Used as: Division Two  Level Two:
The first part of this task is rather boring, we have to parse the input to get the description of the circles. If (in addition to the conditions in the problem statement) somebody told us the color of each of the circles, the task would be pretty simple: add the areas of all white circles and subtract the areas of all black circles to get the result. (If you don't see this immediately, imagine the order in which the circles are actually drawn and keep track of the total white area. Each time a white circle is drawn, it is drawn on a completely black background, thus you add its area to the total white area. Similarly, each time a black circle is drawn, you subtract its area from the total white area. The final result of a summation doesn't depend on the order in which we sum the elements.) So all we have to do is to be able to tell the color of each of the circles. How to do it? Fix a circle C. In the moment we are going to draw C, all larger circles have already been drawn. If C lies in none of them, it will be white. If it lies in one of them, it will be black. If it lies in two of them, the outer one is white, the inner one is black, thus C has to be white again. And so on. Thus the color of C depends on the parity of the number of circles that contain C. Here we come to the last problem: How shall we check whether a circle Q contains our circle C? As the circles don't intersect each other, it is enough to check whether the centre of C lies inside Q, in other words whether (X_{Q}X_{C})^{2} + (Y_{Q}Y_{C})^{2} < R_{Q}^{2} // count, centers and radii of the circles int N, X[64], Y[64], R[64]; // check whether circle C is inside circle Q int inside(int C, int Q) { int dx = X[Q]  X[C]; int dy = Y[Q]  Y[C]; return (dx*dx + dy*dy < R[Q]*R[Q]); } double area(vectorOneFight Used as: Division Two  Level Three: Used as: Division One  Level One:
Clearly it doesn't make sense to start killing monster A, stop after a few slashes, go to kill monster B and at some later point return to finish monster A. If we start by killing B and only then go after A, the total amount of damage we take will be less, as B dies sooner. Thus we will surely kill the monsters one after another. The only problem left: in what order shall we do it? As the easy Division 1 problems sometimes go, there were two ways of doing this: one that required thinking and one that didn't. Let's start with the second one. There are at most 10! = 3628800 permutations of the monsters (i.e., ways to order them). It is possible to check them all and select the best one. C++ code follows: int N = damage.size(); // N  the count of monsters int totalDamage = 0; for (int j=0; j<N; j++) totalDamage += damage[j]; vector<int> perm(N); for (int i=0; i<N; i++) perm[i] = i; // generate the first permutation int result = 987654321; do { int damageThisStep = totalDamage; int damageTaken = 0; for (int i=0; i<N; i++) { int monsterToKill = perm[i]; // ceiling(a/b) is computed as (a+b1)/b using ints only int stepsNeeded = (life[ monsterToKill ] + yourDamage  1) / yourDamage; damageTaken += steps * damageThisStep; damageThisStep = damage[ monsterToKill ]; } result = min( result, damageTaken ); } while (next_permutation(perm.begin(), perm.end() )); return result+1; To find the efficient way of solving this task, first consider the case with two monsters, the first one needing H1 hits to die and doing D1 damage each turn, the second one with parameters H2 and D2. If we kill monster 1 first, the total damage we take will be H1*(D1+D2) + H2*D2. If we kill monster 2 first, the total damage we take will be H2*(D1+D2) + H1*D1. Clearly we should start with the first monster if H1*D2 is less than (or equal to) H2*D1. Or equivalently, if (H1/D1) ≤ (H2/D2). Now consider the general case. We claim that it is optimal to sort the monsters by (Hi/Di) and kill them in this order. Proof: Consider any solution that's not sorted. Clearly we can find two consecutive monsters that don't obey the order. By swapping these two monsters we can improve the solution – we will get less total damage from these two, the amount of damage taken from the other monsters won't change. The conclusion: Any solution that isn't sorted can be improved, and thus it isn't optimal. The only solution that can be optimal (and therefore is optimal) is the sorted one. When doing the sorting, it is good practice to avoid using real numbers. Instead of comparing double(H1)/D1 and double(H2)/D2, compare H1*D2 and H2*D1. GameEndingUsed as: Division One  Level Two:
All we need to know here is a bit of combinatorial game theory. We will call a position winning if the player that's going to make the next move has a strategy that will guarantee him winning the game regardless of what his opponent does. We will call all the other positions losing. (Note that if a player is in a losing position, then his opponent has to have a winning strategy.) We can give a simple recursive definition of winning and losing positions:
We can rewrite this definition into a simple recursive procedure. Due to the constraints in the problem statement this solution was fast enough to solve all valid inputs in time. int piece[10][2]; // locations of the pieces int N, M; // the dimension of the board, the current number of pieces in play // check whether pieces i and j attack each other int attacks(int i, int j) { int dx = abs(piece[i][0]  piece[j][0]); int dy = abs(piece[i][1]  piece[j][1]); if (dx == 0) return 1; if (dy == 0) return 1; if (dx == 2 && dy == 1) return 1; if (dx == 1 && dy == 2) return 1; return 0; } int playerOnMoveWins() { M++; // try all possible moves for (int i=0; i<N; i++) for (int j=0; j<N; j++) { // add a new piece piece[M1][0] = i; piece[M1][1] = j; // check whether this is a valid move int ok=1; for (int k=0; k<M1; k++) if (attacks(k,M1)) { ok=0; break; } if (!ok) continue; // if the move is valid, evaluate the new position recursively if (!playerOnMoveWins()) { // we found a valid move M; // don't forget things like this when leaving recursion! // (this is the bug I made in the SRM :P ) return 1; } } // no move will guarantee winning the game, we lose M; return 0; } string result(int n, vectorConvexHull Used as: Division One  Level Three:
First of all let's consider a simpler problem: Let P_{0}, P_{1}, ..., P_{k} be points determining a polyline such that:
These conditions describe exactly those polylines that can be used as "one quarter of a convex polygon". We will call them boundary polylines. We will be interesting in maximizing k, given X and Y. Let best[X][Y] be the largest number of points a boundary polyline from [0,0] to [X,Y] can have. We will show how to compute these values. Consider an arbitrary [X,Y]boundary polyline. Let dx_{i} = x_{i+1}  x_{i}, dy_{i} similarly. Let gcd(x,y) denote the greatest common divisor of the numbers x, y. If for some i gcd(dx_{i},dy_{i})=d>1, we can make this segment d times shorter, thereby obtaining a [X',Y']boundary polyline with the same number of points (and X'≤X, Y'<Y). Thus each boundary polyline can be reduced into a shorter boundary polyline, that has the same number of points and dx and dy for all its segments are relatively prime. We will call such polylines basic. On the other hand, any [X,Y]boundary polyline can easily be extended to get a [X',Y']boundary polyline (with X'≥X, Y'≥Y) – just make the first segment longer and the last segment taller. What follows that best[X][Y] = number of points on the best basic [X',Y'] polyline for some X'≤X, Y'≤ Y. (Clearly best[X][Y] can't be larger, because we can reduce the best polyline to some basic one. On the other hand, the best basic polyline can be extended to get a valid [X,Y]polyline.) Thus it is enough to generate basic boundary polylines. For each [X,Y] we will compute the maximum number of points on a [X,Y]basic boundary polyline. We will use dynamic programming to do this. To make sure that the slope of line increases, we will process the possible vectors [dx,dy] in increasing slope order, each time extending the currently best polylines by another segment. Moreover, we can note that if sometimes we may decrease dx or dy of a segment of a polyline without violating the slope condition. In that case, we get a shorter polyline with the same number of points again. As a consequence, it can be shown that it is enough to consider basic polylines with segments having dx,dy≤25. The proof is left as an exercise for the reader ;) [Hint: consider the total dx and dy for all such vectors.] The following code computes the array bestBasic[][], where bestBasic[X][Y] is the length of the best basic [X,Y]boundary polyline that can be assembled from the considered set of vectors. We claim that for any [X,Y] an optimal boundary polyline can be constructed by extending one of these polylines. typedef pair Now we simply compute the desired array best[][]: for (int i=0; i≤200; i++) for (int j=0; j≤200; j++) { best[i][j] = max(2, bestBasic[i][j]); // 2 is a straight line segment if (i==0 && j==0) best[i][j] = 1; // either we already have the optimal solution, // or we get it by extending some other optimal solution if (i) best[i][j] >?= best[i1][j]; if (j) best[i][j] >?= best[i][j1]; } } Now we are left with the final step: How to find the best polygon? We will assemble it from four boundary polylines. Similarly as in the polyline case, an optimal polygon can always be extended to touch all four sides of the rectangle. What we have to find are four points (one of each of the sides of the rectangle) that divide the boundary of the polygon into four boundary lines. There are too many possibilities to employ brute force, thus we will use dynamic programming. We will try all possibilities for the placement of the first point P1. For each point P2 on the second side, compute the best number of points on a boundary polyline from P1 to P2. Then, for each point P3 on the third side compute the best total number of points on a boundary starting in P1, going through some P2 and ending in P3. Do the same for all P4 on the fourth side and choose the possibility that (together with the optimal boundary polyline from P1 to P4) gives the maximal number of points. An important "catch" in the problem was that sometimes it is useful to have a corner of the polygon in the corner of the rectangle. As example 2 in the problem statement claims, the best polygon for m=n=4 has got 9 vertices – and it is impossible to make it without placing one of its vertices into the corner. 
