 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
|||||||||
| ||||||||||
|
||||||||||
| ||||||||||
|
||||||||||
|
Eryx Wins Room 2
RingCountby lbackstromWe start with the outermost ring (of '.'s) and work our way in. At each new ring, we perform a flood fill to find all the characters of the same type that are connected orthogonally. As we do this, we assign all of the characters in each ring (where a ring may be '.'s or 'X's here) a number, counting from the outside in. If the bitmap is valid, then each character will be adjacent (both orthogonally and diagonally) to characters that have either the same number, a number one higher or a number one lower, since each character must be adjacent to characters in the same ring, the ring surrounding them, or the ring immediately inside them. If a character was adjacent to another character whose number differed by more than 1, then there would have to be a break in either the ring immediately outside of it, or immediately inside of it. So, the algorithm ends up being very simple:
number = 1
if(border is not '.'s)return -1
for(i = 0 to sizeof(bitmap)-1)
for(j = 0 to sizeof(bitmap[i])-1)
if(!assigned[i][j])
flood_fill(i,j,number++)
for(i = 0 to sizeof(bitmap)-1)
for(j = 0 to sizeof(bitmap[i])-1)
for(di = -1 to 1)
for(dj = -1 to 1)
if(i+di and j+dj are in range and
abs(assigned[i][j]-assigned[i+di][j+dj]) > 1)
return -1
if(number % 2 == 1)return -1;//innermost ring is '.'s
else return number/2
AreaSplit
by gepa
Since the blue pattern is a shifted version of the red one, each square in the red pattern has a corresponding blue square that is at a distance (dx, dy) relative to the red one, for some constant dx and dy. The main idea of the algorithm is to iterate over all possible values of (dx, dy) and check if a solution exists. If one is found (this will be unique, see below), it has to be compared with previously found solutions to resolve any tie-breakers. First thing to notice is that if we can split the given pattern into two half-patterns, it is not important which of the two is colored red and which one blue. So we can begin by coloring one random square red (i.e., the half-pattern, to which this square ends up belonging, will be defined to be the red one). The square of the blue pattern corresponding to the square we just marked red will be any of the remaining white squares, so we iterate over these squares and check for a solution. Until now we have marked one square red and one blue, corresponding to the same position in their respective half-pattern, so that we can deduce the distance (dx, dy) between the two half patterns. For any square at a position (x, y) that we mark red, we have to mark the square at position (x + dx, y + dy) blue, and for any square at a position (x, y) that we mark blue, we have to mark the square at position (x - dx, y - dy) red. Noticing this, we can construct a solution by iterating over all remaining white squares and checking if it is possible to mark this red (i.e., the square at a distance (dx, dy) relative to this is also white) or blue (i.e., the square at a distance (-dx, -dy) relative to this is also white). If neither is possible for some square, then we break, since a coloring with this (dx, dy) is not possible. If exactly one of these (red/blue) is possible, then we mark this one red/blue and the corresponding one blue/red, and continue with another white square. If both of these (red/blue) are possible, then we continue with another white square, and leave this for later to check again. Remains to show that this coloring procedure will eventually terminate, i.e., if there is still a white square to check, there will always be at least one square that can not be colored both red and blue. In fact, if (x, y) is white, then there will be a maximum n >= 0 with (x + n * dx, y + n * dy) being also white and (x + (n + 1) * dx, y + (n + 1) * dy) not white. That means that (x + n * dx, y + n * dy) can not be colored red, so this will either lead the algorithm to a break (no pattern split possible for this dx, dy), or reduce the number of white squares by 2 (coloring this one blue and the corresponding one red). This also shows that if we check the white squares in order (e.g. row by row, from left to right), we will always either be able to color this or break this (dx, dy)-check with no solution, making the coloring procedure efficient and helping avoid timeouts (the reasoning for this is that either (x+dx, y+dy) or (x-dx, y-dy) will be in a previous row or in the same row further left, i.e., a square we have already painted). When we have found a solution, we just need to crop the leftmost/rightmost columns and the uppermost/lowermost rows that do not contain any red square, and do the tie-breaker checks described in the problem description comparing this solution to the best solution found so far, and in the end return the best found solution (or an empty String[] if no solution was found). The following pseudo-code describes the algorithm:
String[] best = new String[0]; // The best solution found so far.
Set board[x0][y0] = 'R' for some arbitrary (x0, y0) with board[x0][y0] == '#'
Iterate over all (x,y) with board[x][y] = '#' {
// deep copy board to a local variable
String[] copy = board.clone();
copy[x][y] = 'B';
dx = x - x0;
dy = y - y0;
// do the following iteration in order, e.g. row by row, left to right
Iterate over all (x1, y1) with copy[x1][y1] = '#' {
boolean canBeRed = false;
boolean canBeBlue = false;
if (copy[x1 + dx][y1 + dy] == '#') {
canBeRed = true;
}
if (copy[x1 - dx][y1 - dy] == '#') {
canBeBlue = true;
}
if ((canBeRed == false) && (canBeBlue == false)) {
continue with next (x,y);
}
if ((canBeRed == true) && (canBeBlue == false)) {
copy[x1][y1] = 'R';
copy[x1 + dx][y1 + dy] = 'B';
if ((canBeRed == false) && (canBeBlue == true)) {
copy[x1][y1] = 'B';
copy[x1 - dx][y1 - dy] = 'R';
}
if ((canBeRed == true) && (canBeBlue == true)) {
// this can not happen if we iterate (x1,y1) in order.
}
}
Change every 'R' into an '#' and every 'B' into an '.' in copy.
Crop copy to the smallest rectangle that contains all '#' characters.
If best is not empty and has less columns than copy continue with next (x,y)
If best is not empty, has the same width as copy but less rows continue with next (x,y)
If best is not empty, has the same width and height as copy and comes earlier
lexicographically than copy, continue with next (x,y)
Set best = copy;
}
return best;
RandomChoice
by gepa
probH(nHH, nHT, nTH, nTT) = pH * (pHH ^ nHH) * (pHT ^ nHT) * (pTH ^ nTH) * (pTT ^ nTT) probT(nHH, nHT, nTH, nTT) = pT * (pHH ^ nHH) * (pHT ^ nHT) * (pTH ^ nTH) * (pTT ^ nTT)
The first one (
For two outcomes to have the same probability of occuring, they shall
share the same countH(nHH, nHT, nTH, nTT) countT(nHH, nHT, nTH, nTT)If we have these functions (see further down for how these can be computed), the basic idea of the solution is to iterate over all possible nHH, nHT, nTH
and nTH, and add the following probability to the result
(which is to be initialised to 0.0 at the beginning):
p += (countH(nHH, nHT, nTH, nTT) / k) * k * probH(nHH, nHT, nTH, nTT); p += (countT(nHH, nHT, nTH, nTT) / k) * k * probT(nHH, nHT, nTH, nTT);
(
Since each of
double p = 0.0;
for (nHH = 0; nHH < n; nHH++) {
for (nHT = 0; nHT < n; nHT++) {
// Case 1: First throw is Heads, last throw is Heads
nH = nHT + nHH + 1 // (total number of Heads)
nT = n - nH = n - nHT - nHH - 1 //(total number of Tails)
nTH = nHT
nTT = n - nHT - nHH - 1 - nTH // ( = nT - nTH)
p += (countH(nHH, nHT, nTH, nTT) / k) * k * probH(nHH, nHT, nTH, nTT);
// Case 2: First throw is Heads, last throw is Tails
nH = nHT + nHH
nT = n - nH = n - nHT - nHH
nTH = nHT - 1
nTT = n - nHT - nHH - nTH - 1 // ( = nT - nTH - 1)
p += (countH(nHH, nHT, nTH, nTT) / k) * k * probH(nHH, nHT, nTH, nTT);
// Case 3: First throw is Tails, last throw is Heads
nH = nHT + nHH + 1
nT = n - nH = n - nHT - nHH - 1
nTH = nHT + 1
nTT = n - nHT - nHH - 1 - nTH // ( = nT - nTH)
p += (countT(nHH, nHT, nTH, nTT) / k) * k * probT(nHH, nHT, nTH, nTT);
// Case 4: First throw is Tails, last throw is Tails
nH = nHT + nHH
nT = n - nH = n - nHT - nHH
nTH = nHT
nTT = n - nHT - nHH - nTH - 1 // ( = nT - nTH - 1)
p += (countT(nHH, nHT, nTH, nTT) / k) * k * probT(nHH, nHT, nTH, nTT);
}
}
return p;
Remains to compute
In the above formulas, |
|
