misof wins Room 3

Discuss this match
Thursday, October 13, 2005
Introduction by FogleBird

Everyone can go home feeling content after the Room 3 portion of the on-site finals here at the 2005 TopCoder Open. Each of the sixteen competitors submitted a correct 250-point solution, leaving each of them with a positive final score. The relatively easy 250 left plenty of time for thirteen of the coders to submit the 500-point problem. However, only three of them ended up passing - four were brought down during the challenge phase and the rest during system tests. Finally, misof was the only one to submit the difficult 1000-point problem. He seemed rather excited as his solution passed system tests, keeping him in 1st place for the room. He and nicka81 will advance to the finals tomorrow. ivan_metelsky, antimatter, marian, and kalmakka will move on to the wildcard round for a second chance to make it into the final championship round. Good luck!


by brett1479

Here we must compute the probability that a given number will occur most frequently. The friendly constraints guarantee there will be at most 5 different values, and at most 15 numbers generated. Looping through all possible counts for each value, we see there are at most C(19,4)=3876 (read "19 choose 4") ways to choose the values. If we only consider the ways where the required number occurs most frequently, there are even fewer possibilities to consider. For each set of counts, we can compute the probability of that set occurring. First, fix a particular ordering of the multiset we have chosen (a multiset is a collection of values with different counts). To compute the probability of that ordering, we multiply the probability of getting each value. For example, if
probs = {20,30,50}
and we are considering the multiset
M = { 0 with count 2, 1 with count 1, 2 with count 3 }
with fixed ordering <2,0,1,0,2,2>, then the associated probability is
P = .5*.2*.3*.2*.5*.5
Conveniently, any ordering of these 6 values will occur with the same probability, so the total probability for this set of counts can be computed by multiplying P by the number of orderings of these values. This count is
C = 6!/(2!*1!*3!) = 60
6! represents the number of ways to order 6 distinct objects. The denominator accounts for the duplicates. This formula is called a multinomial coefficient. To complete the task at hand, we sum all of the C*P values (for each possible set of counts), and get our final result.


by lbackstrom

It is useful to think about what happens when n = 1: there is only 1 person and he wants to attend as many meetings as possible. In this case, a simple greedy algorithm is correct. First go to the meeting that gets out earliest. Then, among meetings that are still options, go the the one that gets out earliest, and so on. By always picking the meeting that gets out earliest, you maximize your potential to go to future meetings.

It turns out that you can extend this to the case where n > 1. By having someone go to the meeting that gets out earliest, you maximize that person's ability to go to future meetings. As long as you iteratively assign the meetings, always picking the one that ends earliest out of your available options, you'll end up covering the most meetings possible. All that remains is to figure out which meetings are still possible, given that some meetings have already been selected.

One way to do this is to assign people to meetings as the meetings are selected. Number the people from 1 to n, and whenever you select a meeting, assign it to the person who is done with other meetings latest, but doesn't have a conflict with that meeting. If you do this, you will always assign the meetings to people in such a way that you are maximizing the ability of the group to go to future meetings. Then, during the execution of your algorithm, a meeting is an option if and only if there is some person who doesn't have any conflict with it, assuming that you assign meetings in order by ending time.

Note that one incorrect way to do this (which cost many coders), is to simply count the number of conflicts that each meeting has with previously assigned meetings. While this is temptingly simple, it has the unfortunate property that it fails. Image a meeting from 8-9, 9-10 and 8:30-11, and two people. We examine the meetings in order by end time, and find that we can go to both of the first two meetings. Now, we look at the 8:30-11 meeting and see that it conflicts with two previously assigned meetings. Hence, we erroneously conclude that we can't go to the third meeting also.


by gepa

It is easier here to solve the inverse problem, i.e., what is the maximum radius of a disc that we can cover with numDiscs unit discs (radius 1.0). If we have found that, we can scale the solution to the given discRadius, and deduce thus the minimum radius we need for the small discs.

Let's call the maximum radius of a disc that we can cover using n unit discs maxRadius(n). We use dynamic programming to compute maxRadius(n) beginning with n=0 (maxRadius(0)=0) and going up to numDiscs. In order to compute maxRadius(n), we iterate over the number of discs, m, that are used to cover the outermost ring in the optimal solution. Since n-m discs can cover a disc of maximum radius maxRadius(n-m) (which we have computed in previous steps), this will be the inner radius of the outer most ring that we need to cover with the m remaining unit discs. So we need to place the m discs at an optimal distance x from the center (at the vertices of an m-gon as described in the problem statement), such that the ring covered has the maximum possible outer radius, but still covering the circle with radius maxRadius(n-m) (how this is done is explained later). Choosing the value for m that maximizes the outer radius gives us finally maxRadius(n). Noticing that each ring except the innermost one has to be covered by at least 3 rings helps avoiding to handle special cases for m=2 or m=1. In pseudo-code we have:

double minRadius(double discRadius, int numDiscs) {
    double[] maxRadius = new double[numDiscs + 1];
    maxRadius[0] = 0.0;
    maxRadius[1] = 1.0; // just one disc
    maxRadius[2] = 1.0; // a second disc does not help much
    for (int n = 3; n <= numDiscs; n++) {
        // We initialize first maxRadius[n] to the worst value we
        // know that we can achieve.
        maxRadius[n] = maxRadius[n - 1]
        for (int m = 3; m <= n; m++) {
            // addRing(double r0, int m) returns the maximum radius
            // we can cover if we already have a disc with radius r0
            // covered and add m discs covering an additional ring
            // (see below for implementation details).
            double rnext = addRing(maxRadius[n - m], m);
            if (rnext > maxRadius[n]) {
                maxRadius[n] = rnext;
    // With numDiscs discs of radius 1.0 we can cover a disc of radius maxRadius[numDiscs]
    // So, we can cover a disc of radius discRadius using numDiscs discs of radius:
    return discRadius / maxRadius[numDiscs];

Now remains the hard part, implementing the function addRing(r0, m), which computes the optimal way to place m>2 unit discs around the already covered disc with radius r0. As described in the problem statement, we place the m discs centered at the vertices of a regular m-gon, let's say at a distance x from the center. In the figure below, A and B are the centers of two neighbouring of the m unit discs we place. Since we have a regular polygon, the angle AOB (O is the center of the original disc) will be equal to (2 * PI / m); in the following we call 'a' half of this angle, i.e., a = PI / m. Since the m unit discs have to cover at least the circle at distance r0 from O, the point M (the middle of the arc between OA and OB) will have to be covered by the disc centered at A or B (since these are the discs closest to M), i.e., x must be choosen such that AM <= 1.0. This gives us an upper bound for x (see figure for details):

Note that if the term under the square root is negative, i.e., r0 * sin(a) > 1.0, we can not cover the circle r0 with only m additional discs, so we just return r0.

If we place the discs at a distance x, we cover a ring up to an outer radius (see figure):

We want to find the x that maximises this, so the derivative of this term must be set to 0 (to ensure that this is actually a maximum we need to also check the second derivative, but this turns out to be always negative, so we do indeed have a maximum):

If this is within the limit given above for x, then this is the value we need to take for x, otherwise we have to use the maximum allowed x value as given above. Using the formula for rout we can finally return the radius of the disc we can cover with m discs additional to the already covered r0 disc.

In total, we end up with the following code (in Java) for addRing(r0, m)

double addRing(double r0, int m) {
    double a = Math.PI / m;
    double z = 1.0 - r0 * r0 * Math.sin(a) * Math.sin(a);
    if (z < 0) return r0;
    double xmax = r0 * Math.cos(a) + Math.sqrt(z);
    double x = Math.cos(a) / Math.sin(a);
    if (x > xmax) x = xmax;
    return x * Math.cos(a) + Math.sqrt(1.0 - x * x * Math.sin(a) * Math.sin(a));