
Match Editorial 
SRM 242Saturday, 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 challenges!
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 pseudocode:
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[i1] + probs[i1];
}
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 pseudocode:
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[i1]) {
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 (upleft/upright/downleft/downright). 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
8polyominoes).