Tuesday, October 28, 2008 Match summaryThis match featured another conceptual problem set from Vasyl[alphacom]. If in the previous his SRM 403 all problems were about numbers composed of digits 4 and 7, in this SRM all problems were about checkers on rectangular board. Somewhat unexpectedly, the match turned out to be very tough. In Division 1 only 17 coders solved the Medium and only 4 coders solved the Hard. Nobody was able to finish both these problems correctly. nika won his first SRM with correct solutions on first two problems and 275 challenge points. lukasP had the fastest Hard, but got only the second place because of skipped Medium. Petr rounded the Top3. Egor, the author of the fastest Medium, took the fourth place. In Division 2 nobody was able to solve the Hard problem and only 16 coders succeded in solving the Medium. The fastest among them was Secluder, however he didn't get anything during the Challenge phase and took only the second place. The first place was taken by Jasoni86 with 200 challenge points. TT87 with 150 challenge points got the bronze. The ProblemsTheSimpleGameUsed as: Division Two  Level One:
This problem is really straightforward. We need to consider each checker separately and choose the closest corner to it. This is done by calculating the distance from the checker to each of 4 corners and choosing the minimum. The distance between cells (x, y) and (x', y') is equal to x  x' + y  y'. public class TheSimpleGame { public int count(int n, int[] x, int[] y) { int res = 0; int[] cx = new int[] {1, 1, n, n}; int[] cy = new int[] {1, n, 1, n}; for (int i=0; i < x.length; i++) { int dst = 10000; for (int j=0; j < 4; j++) dst = Math.min(dst, Math.abs(x[i]  cx[j]) + Math.abs(y[i]  cy[j])); res += dst; } return res; } }TheTower Used as: Division Two  Level Two: Used as: Division One  Level One:
Let's fix some K and try to find the best way to gather some K checkers in the same cell. To do this, we first consider a very slow approach: iterate through all possible subsets of K checkers and for each subset find the best way to gather all checkers from it in the same cell. The following question immediately arises: how to solve the problem for a fixed subset of K checkers? If we have K checkers located at (x[1], y[1]), ..., (x[k], y[k]) and wish to move them into the cell (x, y), the number of required moves will be (x  x[1] + ... + x  x[k]) + (y  y[1] + ... + y  y[k]) = (x  x[1] + ... + x  x[k]) + (y  y[1] + ... + y  y[k]). The sum is broken into two separate sums, where the first one is dependent only on x and the second one is dependent only on y. It means we can choose x and y independently. Let's show that the best x is one of x[i] (in fact, the best x is the median of all x[i], but we don't need this fact to solve the problem). Sort x[i] in nondescending order: x[1] ≤ ... ≤ x[k]. Suppose that the best x is not one of x[i] and is located between points x[j] and x[j+1]: x[j] < x < x[j+1]. We have j points to the left of x and k  j points to the right. If j < k  j, then changing x to x + 1 will increase the distance to the left points by j and decrease the distance to the right points by k  j. In total the distance will decrease by k  2*j > 0. Similarly, if j > k  j, then changing x to x  1 will decrease the total distance by 2*j  k > 0. So the only case when x can be optimal, is when j = k  j. But in this case the distance is the same on the whole segment [x[j], x[j+1]], so x = x[j] or x = x[j+1] also produce the best total distance. So what we have is that the best meeting point for any subset of checkers is of form (x[i], y[j]), where both x[i] and y[j] are some input coordinates. At the first glance, it doesn't help much because we can't iterate through all subsets of checkers (it can be as much as 2^50 subsets). But the correct idea is near: we can iterate through all possible meeting points (it can be at most 2500 such points)! For each meeting point we will then need to answer the question: which subset of K checker is best gathered at this meeting point? And the answer is simple: this is the subset containing K closest checkers to this meeting point. So finally our solution in pseudocode looks as follows: Fill result array by sufficiently large numbers Iterate through all x[i] Iterate through all y[j] Iterate through all K Choose a subset containing K closest checkers to the cell (x[i], y[j]) Calculate the cost of gathering these checkers in (x[i], y[j]) Set result[K] := min(result[K], cost) Java implementation of this approach follows. import java.util.*; public class TheTower { public int[] count(int[] x, int[] y) { int N = x.length; int[] res = new int[N]; Arrays.fill(res, 1000000000); int[] dst = new int[N]; for (int i=0; i<N; i++) for (int j=0; j<N; j++) { // calculate distance from (x[i], y[j]) to all checkers for (int k=0; k<N; k++) dst[k] = Math.abs(x[i]  x[k]) + Math.abs(y[j]  y[k]); // sort distances Arrays.sort(dst); // for each K choose the subset of K closest checkers int sum = 0; for (int k=0; k<N; k++) { sum += dst[k]; res[k] = Math.min(res[k], sum); } } return res; } }TheEasyChase Used as: Division Two  Level Three: Used as: Division One  Level Two:
Despite very low success rate, this problem is nothing more than standard combinatorial game problem. Though there are two things that make this problem harder:
Let's describe a general way of solving such problems. First, we need to identify the set of states (positions) that can occur during the game. Here the state of the game is vector (white piece position, black piece position, player to do the next move). For each state we need to find the outcome of the game (WIN if the player to do the next move will win, LOSE if this player will lose, DRAW if the game will last infinitely without either player winning). Note that for this game DRAW is impossible, but there are games where some states lead to DRAW. For each state where the outcome is not DRAW we additionally need to calculate the number of moves the game will last. There are two possible approaches to do this calculations. The first one is iterative and the second one is a variation of breadth first search. The first approach works slower, but for this problem both algorithms are fine. The proof of algorithms' correctness is left to the reader, but it's worth noting that both are based on the following simple recursive definitions:
The pseudocode for iterative algorithm is given below (it uses two array  OUTCOME[state] is game's outcome and MOVES[state] is the number of moves before the game's end): Set OUTCOME for all states as UNKNOWN Set OUTCOME to WIN and MOVES to 1 for all states where it's possible to win in 1 move Do the following iteration until there are updates in OUTCOME: Iterate through all states If from some state A there's a move to a state B where OUTCOME[B] = LOSE: Set OUTCOME[A] to WIN Set MOVES[A] to min{MOVES[B]+1} by all B such that a) there's a move from A to B b) OUTCOME[B] = LOSE If all moves from some state A lead to states B where OUTCOME[B] = WIN: Set OUTCOME[A] to LOSE Set MOVES[A] to max{MOVES[B]+1) by all B such that there's a move from A to B For all states where OUTCOME is UNKOWN, set OUTCOME to DRAW Check misof's code for an implementation of similar approach. The complexity of the previous approach can be estimated as O(MAX_MOVES_BEFORE_GAME_FINISH * STATES_NUMBER * MAX_MOVES_FROM_A_SINGLE_STATE). Another approach uses a queue which contains all positions for which outcome is known. Each state is thus visited at most one time and the complexity of the algorithm is O(STATES_NUMBER * MAX_MOVES_FROM_A_SINGLE_STATE). The approach is very similar to breadth first search, of course with some modifications. The pseudocode for it is shown below (it additionally uses one more array NEED; it contains the number of moves to winning positions from a state we still need to find in order to confirm that the outcome for this state is LOSE): Set OUTCOME for all states as UNKNOWN Set NEED for all states as the number of possible from from the state For all states where it's possible to win in 1 move Set OUTCOME to WIN Set MOVES to 1 Put this state into the queue While the queue is not empty Get the state A from the queue For all states B such that there's a move from B to A If OUTCOME[A] is WIN Decrease NEED[B] by 1 If (OUTCOME[A] is LOSE) or (OUTCOME[A] is WIN and NEED[B] is 0) Set OUTCOME[B] to (not OUTCOME[A]) Set MOVES[B] to MOVES[A]+1 Add B to the queue For all states where OUTCOME is UNKNOWN, set OUTCOME to DRAW For a challenge submission using this approach take a look at Petr's solution. You can also find this and this threads about this problem helpful. Excercise. Initially this problem allowed n up to 50. How to solve the problem under such constraints? Note that even the second described approach will be too slow. TheBeautifulBoardUsed as: Division One  Level Three:
Main difficulty in this problem comes from the necessity to count different checkers placements as equal if they become the same after one or several board rotations. Note that each placement becomes the same after 4 board rotations, however some placements repeat themselves after 2 or even 1 board rotations. Let's denote the number of placements that require at least 4 rotations to repeat themselves as C4, that require at least 2 rotations  as C2 and that require just 1 rotation  as C1. It's not hard to see that all C4 placements are broken into groups of four, where all placements within a group are the same, all C2 placements are broken into the pairs of the same placements, and all C1 placements are distinct. Therefore, the total number of distinct placements is C4/4 + C2/2 + C1. Now, let's denote the number of placements that become the same after 4 rotations (this includes those placements that become the same after 2 or 1 rotations) as T4, that become the same after 2 rotations (including those that become the same after 1 rotation) as T2, and that become the same after 1 rotation as T1. T and C values are connected as follows: T4 = C4 + C2 + C1 T2 = C2 + C1 T1 = C1 <=> C1 = T1 C2 = T2  T1 C4 = T4  T2 So, it's enough for us to calculate T1, T2 and T4. First let's calculate T4, i.e. the number of all possible placements. Denote the number of checkers we have of each color as ch[0], ..., ch[k1]. If n^2 < ch[0] + ... + ch[k1], then there's no possible placements and we can return 0. Otherwise, there are C(n^2, ch[0]) ways to put checkers of color 0, C(n^2  ch[0], ch[1]) ways to put checkers of color 1 on the remaining positions, and so on. Here C(N, M) is the number of ways to choose M positions from N, i.e. N! / (M! * (NM)!). We get the following formula for T4: T4 = C(n^2, ch(0)) * C(n^2ch[0], ch[1]) * ... * C(n^2ch[0]...ch[k2], ch[k1]) = n^2 * (n^2  1) * ... * (n^2  ch[0]  ...  ch[k1] + 1) =  ch[0]! * ch[1]! * ... * ch[k1]! We will need to do similar calculations several more times, so let's denote the number of ways to put objects of k colors where there are ch[i] object of color i onto N positions as choose(N, ch[0], ..., ch[k1]). So T4 = choose(n^2, ch[0], ..., ch[k1]). Now let's calculate T2. To do this, note that all cells of the board are broken into pairs of cells that come into each other after 2 rotations. The only exception is the case when n is odd, in this case the central cell always remains the same after rotation and the other cells are still broken into pairs. In order for a placement to repeat itself after two rotations, we need to ensure for each pair that either both cells in it contain checkers of the same color or both cells in it are empty. We have 2 possible cases here:
Calculation of T1 is similar. All cells are broken into groups of four (except central cell for odd n) and all cells within a group must be either empty or filled by checkers of the same color. This gives the following cases:
One final note is that for calculation of choose it's useful to precalculate inversions of all factorials upto 100,000!. To calculate inversion of an integer X it's helpful to apply Small Fermat Theorem: inv(X) = X^1234567889 MOD 1234567891 (note that 1234567891 is a prime number). Java implementation of this approach follows. In this implementation I tried to treat calculations of T1, T2 and T4 in a similar way. public class TheBeautifulBoard { final long MODULE = 1234567891; long[] inv = new long[100001]; // a^b MOD 1234567891 long pow(long a, long b) { if (b==0) return 1; long x = pow(a, b/2); x = (x * x) % MODULE; if (b % 2 == 1) x = (x * a) % MODULE; return x; } // multiplicative inversion of x long calcInv(long x) { return pow(x, MODULE2); } // calculating choose(all, cnt[0], ..., cnt[k1]) long choose(long all, int[] cnt) { long res = 1; long sum = 0; for (int i=0; i < cnt.length; i++) sum += cnt[i]; all %= MODULE; for (int i=0; i < sum; i++) { res = (res * all) % MODULE; all; if (all<0) all += MODULE; } for (int i=0; i < cnt.length; i++) for (int j=1; j <= cnt[i]; j++) res = (res * inv[j]) % MODULE; return res; } // calculates T based on a parameter rot // rot = 4 gives T1 // rot = 2 gives T2 // rot = 1 gives T4 long calcT(long n, int[] A, int rot) { int C1 = 0; for (int i=0; i < A.length; i++) { if (A[i] % rot > 1) return 0; if (A[i] % rot == 1) C1++; } if (C1 > 1) return 0; if (C1 == 1 && n % 2 == 0) return 0; for (int i=0; i < A.length; i++) A[i] /= rot; return choose(n * n / rot, A); } public int count(int n, int[] A) { // precalculate inversions for (int i=1; i<=100000; i++) inv[i] = calcInv(i); // checking whether all checkers fit onto the board long all = (long)n * (long)n; int sum = 0; for (int i=0; i < A.length; i++) sum += A[i]; if (sum > all) return 0; // calculate T long T1 = calcT(n, A.clone(), 4); long T2 = calcT(n, A.clone(), 2); long T4 = calcT(n, A.clone(), 1); // calculate C long C1 = T1, C2 = T2  T1, C4 = T4  T2; while (C2 < 0) C2 += MODULE; while (C4 < 0) C4 += MODULE; // calculate answer long res = C1; res = (res + C2 * inv[2]) % MODULE; res = (res + C4 * inv[4]) % MODULE; return (int)res; } } 
