Algorithm Competition Room 2 Summary
Tuesday, May 13, 2008
Introduction by ivan_metelsky
vlad89 wins Room 2!
The Algorithm Competition of TCO'08 continued with Semifinal Room 2. The actions started early as Eryx submitted the Easy for 243,28 points. Many other competitors followed closely behind. Some time later Eryx found a bug in his code and resubmitted to let the lead to Petr, who quickly made his lead stronger by fast 500 submission. Poles tomekkulczynski and Eryx had also quite good times on the Medium soon after Petr. But the following 15 minutes without submission on 500 showed that the Medium problem was not very easy. Still, it was not very hard, too, so more submissions on it were made and we saw 12 submissions by the end of coding phase.
Nobody was able to solve the Hard problem during the first 60 minutes. After that, we saw almost simultaneous submissions from Petr and Eryx, and submission from Alexus followed quite soon. Things became more interesting, when Petr resubmitted his Hard and lose the lead. And they became even more interesting when submissions on 1000-pointer from vlad89, Psyho and jakubr came in moving Petr to 5-th place and making it possible the Wildcard duel between Petr and tomek.
During the challenge phase the leader changed 3 times. At the beginning it was Eryx, then vlad89, then Eryx, and again vlad89. There were totally 3 successful challenges on the Easy, one on the Medium and 2 on the Hard. Systests didn't change the first three places, but were essential to determine the Wildcard round advancers. vlad89 won the room, Eryx took second place and Petr finished on third. tomekkulczynski, pashka, Psyho and Alexus advanced to the Wildcard.
Congratulations to all advancers and good luck in the next round!
by misof
FairDiceGame
For this problem, there is a pretty obvious greedy strategy: We will construct the fair sequence of turns sequentially, turn after turn. For each player X we will keep the probability qX that he already won. Initially, these probabilities are all set to zero.
The probability of winning exactly in turn T is
pT = (5/6)T-1 * (1/6).
We will assign this turn to the first player X such that qX+pT ≤
1/playerCount.
There are two issues to consider. First, note that p1=1/6. If there are more than six players, the player that takes the first turn will win the game with probability at least 1/6, which is more than 1/playerCount. Thus for more than six players there is no fair sequence of turns.
Second, we need to convince ourselves that this greedy strategy actually works for 6 or less players. What could go wrong? It could happen that after, say, 47 turns, we would get a situation where all qX are approximately equal, and p48 is larger than each of the values (1/playerCount)-qX. In such a situation we would not be able to assign turn 48 to any of the players.
Luckily, this is not the case. To see why it is so, first note the following fact: Suppose that the game just reached some turn T. With probability 1/6 the game will end in this turn, with probability 5/6 it will go on and end in some later turn. Thus for each T the probability that the game has more than T turns is 5 times larger than the probability that the game has exactly T turns.
For each player X, let rX = (1/playerCount)-qX. At any moment, the sum of all rX is exactly equal to the remaining, unassigned probability.
As we noted above, in each turn we assign exactly 1/6 of the remaining probability to one of the players. However, we know that the remaining probability is equal to the sum of all rX. And as there are at most 6 players, the largest rX is at least equal to 1/6 of the remaining probability. Thus there is always at least one player who can take the next turn.
For the given limit on the number of turns, we can multiply all probabilities by 6maximumTurn, and do all computations in exact, 64-bit integers. However, the limits are so low that even a solution that uses doubles should be precise enough.
IsoscelesTriangle
Without loss of generality we can assume that triangle's points must be located not in centers of rectangular grid cells, but in lattice points (x, y) such that 0 ≤ x < N and 0 ≤ y < M.
First of all, let's prove that we can't construct an equilateral triangle with all its 3 vertices in lattice points. Suppose, we're able to construct such triangle ABC. If d is the length of triangle's side, then the triangle's area can be calculated as d2 * sqrt(3) / 4. As d2 is an integer, the area is irrational. From the other view, we can calculate the area as half the absolute value of the cross product of vectors AB and AC (see "Cross product" section of the geometry tutorial for clarification). From this way of calculation it follows that the area is rational. Obviously, the same number can't be rational and irrational at the same time, so equilateral triangles are not possible.
The proven fact means that we can restrict ourselves to only triangles which are isosceles, but not equilateral. Let ABC be an isosceles triangle with |AB| = |AC| = L. If vector AB has coordinates (dx1, dy1) and vector AC has coordinates (dx2, dy2), then the equality dx12 + dy12 = dx22 + dy22 holds. Assuming that N is the height of input grid and M is its width, there are the following obvious bounds for dx1, dx2, dy1, dy2: - (N - 1) ≤ dx1, dx2 ≤ N - 1, - (M - 1) ≤ dy1, dy2 ≤ M - 1. We start our algorithm by iterating through the all possible values of dx and dy within these bounds and breaking all vectors (dx, dy) into groups with constant value of dx2 + dy2.
Now, obviously both vectors (dx1, dy1) and (dx2, dy2) must lie in the same group. So we iterate through all pairs of vectors (dx1, dy1) and (dx2, dy2) lying in the same group and for each pair we need to determine the number of possible placements of point A such that the whole triangle ABC lies completely inside the given lattice grid. Suppose that A is placed at (x, y), then B must be placed at (x + dx1, y + dy1) and C must be placed at (x + dx2, y + dy2). Let's write inequalities for all coordinates to ensure they all have allowed values:
0 ≤ x ≤ N - 1, 0 ≤ y ≤ M - 1 0 ≤ x + dx1 ≤ N - 1 0 ≤ y + dy1 ≤ M - 1 0 ≤ y + dx2 ≤ N - 1 0 ≤ y + dy2 ≤ M - 1
Simplification of these inequalities gives:
minX = max(0, -dx1, -dx2) ≤ x ≤ min(N - 1, N - 1 - dx1, N - 1 - dx2) = maxX minY = max(0, -dy1, -dy2) ≤ y ≤ max(M - 1, M - 1 - dy1, M - 1 - dy2) = maxY
Now it's not hard to see that there are totally (maxX - minX + 1) * (maxY - minY + 1) possible placements of point (x, y). To obtain the answer we need to sum this value for all pairs of vectors (dx1, dy1) and (dx2, dy2). There's only one thing left which we must not forget. We should ignore pairs where dx1 = -dx2 and dy1 = -dy2. Each such pair gives not a triangle, but three points lying on the same line.
Note that any equilateral triangle would be counted 3 times instead of 1 in the described method, but it doesn't really matter as we've already proved that equilateral triangles are not possible.
by misof
ColorfulBalls
If we denote the total number of balls as N, each state of the game can be represented as an integer partition of the number N. For example, if N=10, one possible partition is 1+1+3+5. This partition corresponds to the state where there are balls of four colors, one color is represented 5 times, one 3 times, and the remaining two colors have one ball each. Note that if we just need the expected number of turns, we don't care which color is which.
The number of partitions grows exponentially, but not too quickly. For N=24 the total number of partitions is just 1575.
As with many similar problems that correspond to Markov processes, the expected number of turns can be computed for all the states at once by solving a system of linear equations.
These equations can be computed in the following way: For example, consider the state 1+4. There are 5*4=20 ways how the first turn can look like. In 12 of these ways nothing happens (we draw two balls of color 2), in 4 we get to the state with all colors equal, and in 4 we get to the state 2+3. Thus for this state we get the equation:
turns(1+4) = 1 + ((12/20)*turns(1+4) + (4/20)*turns(5) + (4/20)*turns(2+3))
The problem with this approach is that we can not afford to use Gaussian elimination to solve the entire system – there can be up to 1575 equations, and the time complexity of Gaussian elimination is Theta(equations3).
There are two ways out. One is a clever and optimized numeric solution, that computes the probability distribution after a lot of steps. If you decide to go this way, you have to make sure that you don't do unnecessary work (e.g., for each state you should pre-compute the list of reachable states), and make enough optimizations to ensure that the number of steps you can afford to simulate within the time limit is sufficient to give the required precision.
The second, more pretty way out, needs one more observation: In each turn the number of colors (=elements in the partition) either stays the same or decreases by 1. Thus we don't have to solve the entire system at once, we can split its solution into smaller parts.
More precisely, we start by setting turns(N)=0. We can now solve a small system of equations to compute all the values turns(a+b). Then another small system of equations to compute all the values turns(a+b+c), and so on. This way, the largest system of equations we will have to solve will have just 400 equations. (This will happen for N=24 when computing the results for partitions into 7 elements from the results for partitions into 6 elements.)
