## Algorithm Competition Room 3 Summary

Tuesday, May 13, 2008

Introduction by ivan_metelsky

### andrewzta wins Room 3!

**
The last Semifinal of this year's TCO turned out to have more complicated problems than two previous ones. However submissions on Easy didn't reflect it.
bmerry was the first to submit the 250-pointer for 237.69 points. He was just 3 points in front
of Soultaker and ardiankp. Many more coders also
submitted the Easy very fast. After that there was a very long silent period of time. Most coders went to the 550-pointer, but some tried the 950-pointer first.
The idea of solution for the 550-pointer was not hard, but it required lengthy and careful implementation. To the contrary, 950-pointer required really
small implementation, but the idea was hard to get.**

**
All coders who tried the 950-pointer first or last gave up and proceeded to 550-pointer. Only marek.cygan tried to
debug his solution till the end of
the coding phase, but he wasn't successful. The submissions on the Medium problem started to came in the second half of the coding phase.
klopyrev was
the first to submit the 550-pointer, and andrewzta followed
closely. After a while ardiankp and overwise
also submitted their Mediums. andrewzta took lead
after klopyrev resubmitted, but the leader changed once more
after bmerry made the
fastest 550-pointer submission. More people submitted their Mediums and by the end of the coding phase there were 15 submissions on it.
**

**
Four 550-pointer submissions were successfully challenged during the challenge phase. marek.cygan and
bmerry scored
additional 50 and 25 points respectively, and these points helped them to advance to the Wildcard round. System tests proved that 5 more submissions on the Medium problem
are also wrong, including the solution by
bmerry. So andrewzta regained the
lead and won his room. ardiankp and
Yarin also advanced to
the Championship round with second and third places, respectively.
SkidanovAlex,
lewha0, marek.cygan and
bmerry will have
hard time fighting for the single advancing
spot in the Wildcard round. With 4 targets competing
and only 1 advancer this round is going to be very hot.**

**
Congratulations to all advancers and good luck in the next round!
**

by SnapDragon

#### WhackAMole

This problem has some theoretically interesting features, but as befits an Easy, all competitors needed to solve it was good old brute force.

Try each possible configuration of moles (in lexicographic order, to help with tiebreaking). For each configuration, try all valid player positions and then see if any rotation of the moles will miss those players. If not, that configuration won't work; move on to the next one. Remember the working configuration with the most moles.

The total runtime, even with a very naive implementation, is 2^10 * 2^10 * 10 * 10, or around 100 million, which will easily run in the time limit. As with many combinatorial problems, using bit manipulation simplifies running through the mole and player configurations. There are many other possible optimizations, but competitors are better served just moving on to the next problem!

Here's Java code for a bit-based approach:

public String placeMoles(int numHoles, int numHammers) { int mask = (1<<numHoles)-1, best_moles = 0, best_mole_bits = 0; try_moles: for (int mole_bits = 0; mole_bits >= mask; mole_bits++) { for (int player_bits = 0; player_bits >= mask; player_bits++) { // Only try player configurations with numHammers players. int num_players = 0; for (int i = 0; i < numHoles; i++) if ((player_bits & (1<<i)) != 0) num_players++; if (num_players != numHammers) continue; // See if any mole rotation works for this player setup. int rotate = 0; for (rotate = 0; rotate < numHoles; rotate++) { int rotated_mole_bits = ((mole_bits << rotate) + (mole_bits >> (numHoles-rotate))) & mask; if ((rotated_mole_bits & player_bits) == 0) break; } if (rotate == numHoles) continue try_moles; // Nope. } // We have a working mole configuration; see if it's better. int num_moles = 0; for (int i = 0; i < numHoles; i++) if ((mole_bits & (1<<i)) != 0) num_moles++; if (num_moles > best_moles) { best_moles = num_moles; best_mole_bits = mole_bits; } } // Convert best configuration from bits to string. String ret = ""; for (int i = numHoles-1; i >= 0; i--) ret += ((best_mole_bits & (1<<i)) == 0) ? 'O' : 'X'; return ret; }

by legakis

#### IncompatibleMice

This problem can be broken into two parts: 1) finding the possible locations in the maze of each mouse at any given time after it starts, and 2) testing if a given set of starting times will result in a possible conflict between the mice.

The simplest way to find the possible locations of a mouse is to run two breadth-first searches, one from its starting location (the "from" search) and a second from its ending location (the "to" search). The distance to the ending square in the "from" search should equal the distance to the starting square in the "to" search. Next, add the distances of corresponding squares of the two searches. Any square with a sum equal to the length of the shortest path is a square the mouse may pass through, at a time equal to the distance in the "from" search after the mouse begins.

Next, you need to test if the mice will conflict, given all possible relative differences between their starting times. One way to make sure you cover all possibilities is to consider all 6 possible orderings of the 3 mice. For each ordering, assume the first mouse starts at time zero. The second mouse can start anywhere from time zero to the length of the first mouse's path. Likewise, the third mouse can start anywhere from time zero to the maximum of the ending times of the first two mice.

If your test for conflict between mice is slow, you can speed it up by testing each pair of mice individually, saving the results for each pair in a one-dimensional array and then using those saved results when testing the possible starting times for all 3 mice. When testing 2 mice with a given time offset, you can make use of the fact that if the offset if even, the mice can only meet in the centers of squares. If the offset is odd, the mice can only meet between two squares. One simple, but more expensive, way to deal with detecting if mice meet between squares is to double the size of the maze in each direction, so that every square center and square edge in the original maze is a square center in the larger maze.

by SnapDragon

#### SequentialThreads

Dynamic Programming is the approach to use for this problem, with a few subtleties that must be properly handled. Here is one method.

The subproblem to be solved is calculating `P(n,t)`

, the
probability that the first `n`

threads will finish after
receiving exactly `t`

time slices (no earlier, no later).
Time slices that go to other threads are ignored for these purposes.

In theory, there is no limit to how many time slices could be required. However, in practice, the probability will become vanishingly small after a certain number. Picking a cutoff time, as high as possible without risking exceeding the runtime limit, is a good way to deal with this. As it turns out, even a cutoff of 1000 works well enough, and the worst case is easy to test if competitors worry about accuracy.

`P(1,t)`

is just 0.0 or 1.0 everywhere, since there's no
doubt how many time slices the first thread will consume before
finishing. The complicated part is computing `P(n,t)`

.

Suppose we know all values of `P(n-1,t)`

. Now, iterate
through all possible numbers of time slices `t`

doled out
to the `n`

threads under consideration. We need to relate
this to the completion times of the left `n-1`

threads in
order to use `P(n-1,t)`

. So, let us call `t`

the time at which the final time slice is sent to the left
`n-1`

threads. What are the odds of this occurring for a
given `t`

?

It is the sum, for each possible `lt`

, of:
[odds that `lt-1`

out of `t-1`

time slices are
sent to those left `n-1`

threads] *
[odds that the final time slice will be sent to the left
`n-1`

threads] *
[odds that those threads will finish after exactly `lt`

time slices].
The second probability is just `(n-1)/n`

, and the third
probability is `P(n-1,lt)`

. As for the first probability,
we can update it for each `lt`

as we run over the
`t`

s, or it can be calculated directly with some
combinatorics.

Note that there's still a little work to do after these `t`

time slices, but not much, because all of the remaining time slices
will be given to the rightmost thread. So we should actually count
each result towards `P(n,t + [remaining time slices])`

,
being careful to handle cases where the `n`

th thread has or
hasn't yet reached its synchronization subtask. After running through
all possible `t`

s, the values for `P(n,t)`

should be as desired.

The final calculation of the average runtime for `n`

threads is the sum of `t*P(n,t)`

. The total runtime is
`O(n*t^2)`

.

Java code follows

:static final int MAXTIME = 2500; public double expectedExecutionTime(String[] threads) { double[] P = new double[MAXTIME]; // Dynamic array for P(n-1,t). P[threads[0].length()] = 1.0; for (int n = 1; n < threads.length; n++) { int sind = threads[n].indexOf('S'), rest = threads[n].length() - sind; double rprob = 1.0/(n+1); // Prob of time slice going to rightmost thread. double[] P2 = new double[MAXTIME+50]; // Dynamic array for P(n,t). double[] lt_prob = new double[MAXTIME+1]; // Probability for each lt. lt_prob[0] = 1.0; for (int t = 1; t < MAXTIME; t++) { // Update P2 using all possibile lt values. for (int lt = 1; lt <= t; lt++) P2[t + Math.max(0, sind-(t-lt)) + rest] += lt_prob[lt-1] * (1.0-rprob) * P[lt]; // Update lt_prob, adding one more time slice. for (int lt = t; lt >= 0; lt--) lt_prob[lt+1] = (1.0-rprob) * lt_prob[lt] + rprob * lt_prob[lt+1]; lt_prob[0] *= rprob; } P = P2; } double ret = 0.0; for (int i = 0; i < MAXTIME; i++) ret += i * P[i]; return ret; }