Member Count: 484,194 - May 23, 2013  [Get Time]
 Match Editorial
SRM 242
Saturday, May 14, 2005

Match summary

In division 1, Petr was in the lead after the coding phase, and remained first despite an unsuccessful challenge. The system tests did not change anything in the top 5, so Petr won the match. Congratulations to him for his first SRM win and an impressive 200 rating point increase, that brought him to the top ten after just 5 contests! Close second came kalinov, and Yarin took the third place.

In division 2, newcomer tomekkulczynski took an impressive first place with over 300 points difference over second placed xnitin and third placed Biskup.

# The Problems

TeamSplit
Used as: Division Two - Level One:
 Value 250 Submission Rate 265 / 279 (94.98%) Success Rate 247 / 265 (93.21%) High Score agray for 248.71 points (2 mins 3 secs) Average Score 215.67 (for 247 correct submissions)

Since the strengths are given in an array in an arbitrary order, we first sort them in descending order. Now we loop through all elements, and add each strength alternating to the team strength of team 1 and team 2, beginning with team 1 (don't forget to initialize team strengths to 0 at the beginning.) Finally, return the difference of the two team strengths.

GuessCard
Used as: Division Two - Level Two:
 Value 500 Submission Rate 135 / 279 (48.39%) Success Rate 87 / 135 (64.44%) High Score tomekkulczynski for 441.52 points (10 mins 37 secs) Average Score 241.90 (for 87 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 208 / 216 (96.30%) Success Rate 148 / 208 (71.15%) High Score jshute for 237.98 points (6 mins 26 secs) Average Score 168.86 (for 148 correct submissions)

With the low constraints for this problem, we can simply solve it by simulating the procedure given in the problem statement.

For this, we can use an `int[][] configuration`, where we store the card numbers in the current configuration (we enumerate the cards from 1 up to `(width * length)` as in the example in the problem statement), and a `boolean[] possible` that represents for each card if it is a possible solution (in the beginning, all elements of this array are true).

Now, we loop through all elements `columns[c]`, and in each step we:

• set `possible[configuration[i][j]]` to `false`, for all `i` and all `j!=columns[c]`.
• if this is not the last element in `columns` rearrange `configuration`.
The rearrangement can be done by "picking up" the cards column by column as stated in the problem statement, and "putting them down" row by row, e.g.:

```k = 0;
for (j = 0; j < width; j++) {
for (i = 0; i < height; i++) {
temp[k] = configuration[i][j];
k++;
}
}
k = 0;
for (i = 0; i < height; i++) {
for (j = 0; j < width; j++) {
configuration[i][j] = temp[k];
k++;
}
}
```

If at the end of the simulation, only one element of `possible[]` is `true`, return the row in `configuration`, where this element can be found.

We can significantly optimize the solution, by noticing that the cards that are possible solutions will always be consecutively put down in each configuration:

Let's enumerate the positions in the layout row by row, beginning with 0 - i.e. position at row `i` and column `j` is called position `(i * width + j)`. In the beginning of each turn, the possible solution cards will be in positions `start` to `stop` for some integers `start` and `stop`. When we are now given the information that the solution is in column `column[c]`, only those cards will be still possible, that are in a position of the form `(row * width + columns[c])` for some integer `row`, and lie in the interval `start` to `stop`. The later condition turns out to be true for `row` in the range from `startrow = (start - columns[c] + width - 1) / width` to `stoprow = (stop - columns[c]) / width` (integer divisions!)

• If this is the last configuration, we return `startrow` if `startrow == stoprow` or `-1` if `startrow != stoprow`.
• If we have more configurations to do, we calculate from `startrow` and `stoprow` the values of `start` and `stop` for the next configuration (see code below), and continue with the next element in `columns[]`.
```int start = 0;
int stop = width * height - 1;
for (int c = 0; c < columns.length; c++) {
int startrow = (start - columns[c] + width - 1) / width;
int stoprow = (stop - columns[c]) / width;
if (c + 1 == columns.length) {
return (startrow == stoprow) ? startrow : (-1);
}
start = columns[c] * height + startrow;
stop = columns[c] * height + stoprow;
}
```

NumberSplit
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 24 / 279 (8.60%) Success Rate 10 / 24 (41.67%) High Score tomekkulczynski for 692.76 points (20 mins 59 secs) Average Score 525.57 (for 10 correct submissions)

The first thing to notice here is that the numbers in every step become smaller. Let's take an example and say we have a five digit number of the form `abcde` (`a`, `b`, `c`, `d` and `e` represent the decimal digits of the number), which we split to produce the successor: `ab * c * de`. Here it is always `c < 10` and `de < 100`, so for the successor we have: `ab * c * de < ab * 10 * 100 = ab000 ≤ abcde`. Similar with any other numbers and splittings.

Now we need a way to compute all possible successors, given a given number. For this we can use the following recursive pseudo-code:

```generateSuccessors(int multiplier, int n) {
add (multiplier * n) to the set of successors
for (i = 10; i <= n; i *= 10) {
generateSuccessors(multiplier * (n / i), n % i);
}
}
```

We initialize the set of successors to an empty set, and call `generateSuccessors(1, n)` (where `n` is the number, for which we want to find the successors). Finally, we remove `n` from the generated set (since this is not a successor of `n` itself, we need to split the given number to at least two parts for a successor to be valid).

To compute the longest possible sequence, starting with the given `start`, generate all successors of `start` as described above, and for each `n` in the successor set compute recursively `longestSequence(n)`. The return value is the maximum of all computed values + 1 (if `start` is a single digit number, the successors set will be empty, and we return 1). Note that this would not work if loops in the sequence were possible, but since each successor is smaller then the original number, this can not happen. In order to avoid a timeout, we need to memorize in a buffer all values already computed.

Alternatively, we can use dynamic programming, by initializing `longest[i] = 1` for all single digit numbers `i`, and computing `longest[i]` from `i = 10` up to `i = start` by adding 1 to the maximum of `longest[j]` for all `j` in the successor set of `i`. This works, since all successors of `i` are smaller than `i`. With this solution, we compute the longest sequence for more numbers than actually needed (many numbers between 1 and `start` can not be reached from `start`) but with the low constraints this solution was within the time limit.

DiceThrows
Used as: Division One - Level Two:
 Value 500 Submission Rate 100 / 216 (46.30%) Success Rate 79 / 100 (79.00%) High Score ploh for 469.69 points (7 mins 18 secs) Average Score 329.44 (for 79 correct submissions)

First we use a helper function to compute for each player the probability that his result is `n`, for all possible outcomes `n`. We can do this by iterating over the number of his throws: For 0 throws, there is a probability of 1.0 that his result is 0 (all other results have probability 0.0). If we have the probabilities for each possible outcome `n` after `i` throws stored in an array `probs[n]`, then we can compute the probability that the outcome after `i + 1` throws is `m` to be: `newprobs[m] = sum over (j = 1 .. 6) probs[m - sides[j]] / 6.0`. Since `sides[j]` is always positive, we can do the whole computation using just one array if we compute `probs[]` in each step starting from higher outcomes and going down:

```double[] getProbabilities(int numDice, int[] sides) {
double[] probs = new double[20001];
// (20000 is the maximum possible outcome with the given constraints.)
probs[0] = 1.0;
for (int i = 0; i < numDice; i++) {
for (int j = 20000; j >= 0; j--) {
probs[j] = 0.0;
for (int k = 0; k < 6; k++) {
if (j - sides[k] >= 0) probs[j] += probs[j - sides[k]] / 6.0;
}
}
}
return probs;
}
```

Using this function, we compute `probsA[]` and `probsB[]`, the probabilities for each outcome for the two players. From `probsB[]`, we compute `probsLowerB[i]`, the probability that the outcome of player B is lower than `i` for each possible outcome `i` iteratively:

```probsLowerB[0] = 0.0;
for (int i = 1; i <= 20000; i++) {
probsLowerB[i] = probsLowerB[i-1] + probs[i-1];
}
```

The probability for player A to win is then the sum of `probsA[i] * probsLowerB[i]` over all possible outcomes `i` (i.e. the probability that player A gets the result `i` and player B gets a lower result, summed over all `i`.)

It turned out that the constraints were low enough that in some optimized cases they also allowed computation of the final result by just iterating over all possible outcomes `i` for player A and all possible outcomes `j < i` for player B, and adding `probsA[i] * probsB[j]`, though this can come too close to the time limit (e.g. in C++ using `vector <double> probsA` instead of `double probsA[20001]` can cause this solution to time out):

```double result = 0.0;
for (int i = 0; i <= 20000; i++) {
for (int j = 0; j < i; j++) {
result += probsA[i] * probsB[j];
}
}
```
PolyominoCut
Used as: Division One - Level Three:
 Value 1000 Submission Rate 6 / 216 (2.78%) Success Rate 6 / 6 (100.00%) High Score Petr for 540.04 points (32 mins 50 secs) Average Score 465.94 (for 6 correct submissions)

The first thing to do here, is to build a set with all possible `k`-polyominoes, ignoring translations (but not rotations and reflections). We can do this by starting with a set that contains the only possible monomino (`k = 1`), and building recursively the more complex polyominoes; in pseudo-code:

```polyominoes[1] = a set containing only a monomino
for (i = 2; i <= k; i++) {
initialize set polyominoes[i] to an empty set
for (all p in polyominoes[i-1]) {
for (all squares s included in p) {
for (all directions d in up/down/left/right) {
if (square in direction d from s is not in p) {
insert (p extended with the square in direction d from s)
into ployominoes[i]
}
}
}
}
}
```

For this, we need a data structure to store our polyominoes. It is convenient here to make a class `Polyomino` for this, which includes either a list of the coordinates that the current polyomino occupies, or an array `boolean[][]` with those elements set to `true` that are occupied by the polyomino. Since we want to ignore translations, we have to define in our data structure, which polyominoes are supposed to be equal, in order for them to not be included in the set a second time (this can be done for example by overriding `equals()` and `hashCode()` in Java, or by overriding `operator==` in C++, where we check if one is a translated version of the other.)

If we didn't have the requirement that the remaining part of the board must be connected, we would be almost ready now. We can place each polyomino `p` from the set `polyominoes[k]` in exactly `(width - p.width + 1) * (height - p.height + 1)` positions in the board, where `p.width` and `p.height` are the width and height that the polyomino `p` occupies (it is useful to store these also in the `Polyomino` data structure while building the polyominoes).

Since we have the additional requirement for the board to remain connected, we have to check this for all possible placements of the polyomino. The constraints of the board clearly do not allow to check all placements explicitly (since there can be more than 1.0e9 valid placements, see last example), but we can easily see that most placements are identical with respect to if they leave the remaining part connected or disconnected. We can find out, that there are 9 possible placements that we have to check: the polyomino being placed somewhere in the center (i.e. leave all edge and corner squares unoccupied), the polyomino being placed at one of the sides (up/down/left/right), and the polyomino being placed at one of the corners (up-left/up-right/down-left/down-right). Since the width and height of the board were chosen to be larger than `k`, we don't have to consider mixed cases (e.g. a polyomino occupying a square in the upper border and in the lower border). So for each of these 9 cases, we check if the remaining board is connected, and if yes, we add the number of positions in the board that are associated with this case:

```polyomino in a center position:  (width - p.width - 1) * (height - p.height - 1)
polyomino in up or down side:    (width - p.width - 1)
polyomino in left or right side: (height - p.height - 1)
polyomino in a corner:           1
```

To check if one positioning of the polyomino is acceptable, we first make a small board that includes the polyomino in the position we want to check: start with the polyomino, and augment it with a line of unoccupied cells on the sides that the polyomino is not supposed to border on (i.e. when checking the "polyomino in the up side" position, we augment the polyomino with a line of squares to the left, right and down). Now we can do a depth first search (or breadth first search) starting in an unoccupied square. If all unoccupied squares are visited, the position is acceptable, otherwise we don't count the position. We have to use a small board for doing the check, since if we used the original board, we would have to do in the worst case `(9 * 2725)` depth/breadth first searches in an 800 times 800 board, which would clearly timeout (2725 is the number of 8-polyominoes).

By gepa
TopCoder Member

 Home  |   About TopCoder  |   Press Room  |   Contact Us  |   Careers  |   Privacy  |   Terms Competitions  |   Cockpit Copyright TopCoder, Inc. 2001-