Tuesday, May 13, 2008
Introduction by ivan_metelsky

Discuss this competition

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 ts, 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 nth thread has or hasn't yet reached its synchronization subtask. After running through all possible ts, 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;
}