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).