Online Round 1B September 23, 2006 Match summaryThis section had the highest number of registrants among all Round 1 sections, with participants including the three most recent TCCC champions. The competition pace was really tough, and only four people were able to submit the hard problem in time. tomek traditionally was ahead after the coding phase, but a bug in the hard problem moved him a dozen positions lower. Only bmerry's and dskloet's hard submissions survived the system tests, giving them the top 2 spots. Eryx, DarLam and gawry rounded the top 5. The ProblemsSpiralsUsed as: Division One  Level One:
Iterating through the cells of a table is easy when you go row by row, but spiral movement is a bit less obvious. To implement it correctly, let's take a closer look at how the spiral is built: Beginning Second Later Even Later Finally 01234 01234 01234 01234 01234 0 ..... ..... ..... 012.. 01234 1 ..... ..... .678. 96789 96789 2 ..0.. ..01. .501. 85010 85010 3 ..... ..... .432. 74321 74321 4 ..... ..... ..... 65432 65432 As you can see, you have to make the following steps to complete the spiral: 1 step  right 1 step  down 2 steps  left 2 steps  up 3 steps  right 3 steps  down 4 steps  left 4 steps  up ....The process is cyclical, and on the ith iteration you have to make (2*i + 1) steps right and down, and (2*i + 2) steps left and up. As soon as any of your steps ends out of the board, you are done. For a clean implementation of this approach, see bmerry's solution: bool go(int dr, int dc, int moves) { for (int x = 0; x < moves; x++) { if (r < 0  r >= (int) ans.size()) return false; if (c < 0  c >= (int) ans[0].size()) return false; ans[r][c] = '0' + p; p = (p + 1) % 10; r += dr; c += dc; } return true; } vectorFactoryCounting Used as: Division One  Level Two:
Your first step should be to reword the problem statement in terms of graph theory. Given a nonoriented graph, you are asked to find the number of different bipartite cliques of size n*m (K_{n,m}). The intended solution for this problem was the brute force approach with some optimizations. The total number of all possible cliques (C(30, 8) * C(22, 8)) is too large to be iterated, therefore we will use a trick  check all possible sets of building factories, and for each set compute the number of different sets of assembling factories. The sum of all these numbers is the answer to our problem. There exist at most C(30, 8) (approx. 6 millions) different sets of building factories, therefore we need to compute the number of proper sets of assembling factories pretty quickly. First, we'll fix a set of building factories X (X_{1}, X_{2},..., X_{n}). Let's call a factory good, if it is connected by a road to all factories X_{1}, X_{2},..., X_{n}. Let's call the set A (factories A_{1}, A_{2},..., A_{m}) good, if sets X and A form a proper factory complex. To satisfy this condition, every factory A_{i} must be connected by a road to all factories X_{j}. Therefore, set A is good if and only if every factory A_{i} is good. Let sets of factories A (factories A_{1}, A_{2},..., A_{m}) and B (B_{1}, B_{2},..., B_{m}) both be good. This means that, for every 1 <= j <= m, factories A_{j} and B_{j} are good. If we merge sets A and B into one set Y (A_{1}, A_{2},..., A_{m}, B_{1}, B_{2},..., B_{m}), all factories in set Y will be good. Therefore, if we take any m factories from set Y, all factories in this new set will be good, and this set will be good itself. As you can see now, any m good factories will form a good set. Therefore, the total number of good sets for set X is equal to C(T, m), where T is the number of good factories for set X. To quickly compute the total number of good factories for set X, you need to use the standard trick with keeping connections for each factory in a bitmask (instead of an array of boolean). The following C++ code implements this approach: // element cnk[i][j] contains the value C(i, j). vectorMonopolies Used as: Division One  Level Three:
The first thing to notice here is that both players are independent, therefore the probability to reach cell i on the jth turn is the same for both players (for any i and j). If we'll be able to find probabilities for a player to reach the cell square in i turns for any i, the return value for the problem can be computed in the following way (prob[i] represents the probability to a player to land on the cell square on the ith turn). double ans = 0; // the probability that the first player hasn't reached // the cell square yet. double first = 1; for (int i = 0; i < 22; i++) { // note that the probabilities to land on the // cell square on the ith turn are independent for all i first = prob[i]; ans += prob[i] * first; // probability that the second player lands on the cell on this turn // and the first player hasn't landed on it yet. } return ans;Since the players can move only forwards (to the cells with higher indices), the probability for a player to reach cell i in j moves depends only on the probabilities for a player to reach cells with lower indices. Therefore, we can iterate through cells from the 0 to 39, calculating the probabilities for cells one by one. The most natural state for this DP is a triple (cell, numbers of moves, number of doubles rolled). Since the player can land on more than 1 cell during a turn (after rolling doubles or drawing a card), we will keep the probabilities for the cell square in a separate array (changing it when the player lands on this cell). Carefully implementing the moves between states, we public class Monopolies { int N = 40, square; int[] move = {11, 24, 29, 39}; int[] probMoves = {0, 0, 0, 2, 2, 4, 4, 6, 4, 4, 2, 2}; int jail = 30; boolean needCard(int s) { return 7 == s  22 == s  36 == s;} public double probability(int square) { double[][][] data = new double[23][N][4]; double[] prob = new double[23]; data[0][0][0] = 1; for (int i = 0; i < 22; i++) { for (int j = 0; j <= square; j++) for (int k = 0; k < 2; k++) { for (int a = 2; a <= 12 && a + j <= square; a += 2) { double p = data[i][j][k] / (36. * 20.); int nxt = j + a; if (nxt == square) prob[i + 1] += p * 20; if (nxt == jail) continue; if (needCard(nxt)) { data[i][nxt][k + 1] += p * 14; for (int q = 0; q < move.length; q++) { if (move[q] < nxt) continue; if (move[q] == square) prob[i + 1] += p; data[i][move[q]][k + 1] += p; } continue; } data[i][nxt][k + 1] += p * 20; } } for (int j = 0; j <= square; j++) for (int k = 0; k < 3; k++) { for (int a = 2; a < probMoves.length && a + j <= square; a++) { double p = data[i][j][k] * probMoves[a] / (36. * 20.); int nxt = j + a; if (nxt == square) prob[i + 1] += p * 20; if (nxt == jail) continue; if (needCard(nxt)) { data[i + 1][nxt][0] += p * 14; for (int q = 0; q < move.length; q++) { if (move[q] < nxt) continue; if (move[q] == square) prob[i + 1] += p; data[i + 1][move[q]][0] += p; } continue; } data[i + 1][nxt][0] += p * 20; } } } double ans = 0; // the probability that the first player hasn't reached the cell square yet. double first = 1; for (int i = 0; i < 22; i++) { // note that the probabilities to land on the cell square // on the ith turn are independent for all i first = prob[i]; // probability that the second player lands on the cell on this turn ans += prob[i] * first; // and the first player hasn't landed on it yet. } return ans; } 
