|
Match Editorial |
Online Round 1-B
September 23, 2006
Match summary
This 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 Problems
Spirals
Used as: Division One - Level One:
Value 250 Submission Rate 461 / 530 (86.98%) Success Rate 325 / 461 (70.50%) High Score kalinov for 246.01 points (3 mins 37 secs) Average Score 171.93 (for 325 correct submissions)
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 i-th 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;
}
vector Spirals::draw(int width, int height, int startx, int starty)
{
.............
r = starty;
c = startx;
p = 0;
int moves = 1;
while (true)
{
if (!go(0, 1, moves))
return ans;
if (!go(1, 0, moves))
return ans;
l++;
if (!go(0, -1, moves))
return ans;
if (!go(-1, 0, moves))
return ans;
l++;
}
FactoryCounting
Used as: Division One - Level Two:
Value 500 Submission Rate 155 / 530 (29.25%) Success Rate 127 / 155 (81.94%) High Score gawry for 467.81 points (7 mins 33 secs) Average Score 293.32 (for 127 correct submissions)
Your first step should be to reword the problem statement in terms of graph theory. Given a non-oriented graph, you are asked to find the number of different bipartite cliques of size n*m (Kn,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 (X1, X2,..., Xn). Let's call a factory good, if it is connected by a road to all factories X1, X2,..., Xn. Let's call the set A (factories A1, A2,..., Am) good, if sets X and A form a proper factory complex. To satisfy this condition, every factory Ai must be connected by a road to all factories Xj. Therefore, set A is good if and only if every factory Ai is good.
Let sets of factories A (factories A1, A2,..., Am) and B (B1, B2,..., Bm) both be good. This means that, for every 1 <= j <= m, factories Aj and Bj are good. If we merge sets A and B into one set Y (A1, A2,..., Am, B1, B2,..., Bm), 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).
vector > cnk;
// element connection[i] contains the bitmask, representing
// all the factories connected to the i-th factory
vector connection;
// computes the number of 1's in the binary code of number i.
int ones(int n) { return n ? 1 + ones(n & (n - 1)) : 0;}
// the core method, which tries adding the current factory or skipping it.
long long go(int factory, int count, int assembly) {
if (count == m)
return cnk[ones(assembly)][n];
if (factory >= N)
return 0;
// move to the next factory
return go(factory + 1, count, assembly) +
go(factory + 1, count + 1, assembly & connection[factory]);
// add the current factory to the list, updating the total count and connections list
}
long long count(int n, int m, vector county)
{
N = county.size(); // the total number of cities
this.m = m; this.n = n;
if (m + n > N) // we definitely can not build the complex
return 0;
connection = vector(N, 0);
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
if (county[i][j] == 'Y') connection[i] |= (1 << j);
cnk= vector >(N + 1, vector(N + 1, 0));
for (int i = 0; i < N; i++) cnk[i][0] = 1;
for (int i = 1; i < N; i++) for (int j = 1; j < N; j++)
cnk[i][j] = cnk[i - 1][j - 1] + cnk[i - 1][j];
return go(0, 0, (1 << N) - 1);
// start from factory 0,
//with total of 0 factories added to the set,
// with all factories "connected" to our empty set.
}
Monopolies
Used as: Division One - Level Three:
Value 1000 Submission Rate 5 / 530 (0.94%) Success Rate 2 / 5 (40.00%) High Score bmerry for 492.70 points (38 mins 29 secs) Average Score 469.64 (for 2 correct submissions)
The first thing to notice here is that both players are independent, therefore the probability to reach cell i on the j-th 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 i-th 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 i-th 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 i-th 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;
}
