Match Editorial

FixTheAverage:

Not surprisingly, this problem did not pose much trouble for Division 2 coders. To compute the number, they simply had to solve the following equation for x:

(a1 + a2 + ... + an + x) / (n+1) = target

The method should multiply target by the size of list plus 1, and subtract the sum of the elements of list from the result.

TileCutting:

This is the infamous problem of SRM 282. It was intended to be a straightforward problem, but very quickly coders began to notice an ambiguity that none of us caught during testing. The ambiguity was whether or not it was legal to cover a half-tile region with two quarter-tile pieces, or to cover an L-shaped region with one half-tile and one quarter-tile piece, or three quarter-tile pieces. For example, given the following layout:

    { "x..x",
      "....",
      "....",
      "x..x" }

it was not clear which of the following two solutions was correct:

	(a)	(b)

The intention was for each region to be covered by the largest possible piece of tile, so (a) above would be the correct solution, requiring 8 cuts. But the problem statement did not explicitly state this, so several people assumed that solution (b) above was legal, which requires only 6 cuts. Incidentally, allowing solution (b) makes the problem more difficult than we originally intended.

Both solutions start out the same way, by analyzing each 2x2 block in layout and counting the number of quarter-tile (Q), half-tile (H), and L-shaped (L) pieces needed. Given these three values, the solution assuming that you may not fill a larger region with smaller pieces can be computed as follows. First match up the minimum of L and Q, countng two cuts for each pair, and then subtract that minimum for each. Then, count two more cuts for each pair of H pieces, and subtract those that you've counted from H. At this point, one (or both) of L and Q will be 0, and H will be either 0 or 1. If Q is zero, then we add 2*(L+H) and we are done. Otherwise, we know L is zero, and we match up the remaining H and Q pieces. The following code performs this computation:

   int calc1(int Q, int H, int L) {

        int ret = 0;

        // match Q and L pieces together:
        while (Q >= 1 && L >= 1) { ret += 2; Q--; L--; }

        // match two H pieces together
        while (H >= 2) { ret += 2; H -= 2; }

        // at this point, H is 0 or 1
        if (Q == 0) {
            ret += (H+L)*2;
        }
        else {
            if (H == 1 && Q >= 2) { ret += 3; H--; Q -= 2; }
            if (H == 1 && Q >= 1) { ret += 3; H--; Q--; }
            if (H == 1) { ret += 2; H--; }
            while (Q >= 4) { ret += 4; Q -= 4; }
            if (Q == 3) ret += 4;
            else if (Q == 2) ret += 3;
            else if (Q == 1) ret += 2;
        }

        return ret;
    }

We can build upon this solution to compute an answer that allows smaller pieces to be put together to fill larger areas. Simply iterate over the number of L-shaped pieces the solution will actually have (from 0 to L, inclusive), replacing L-shaped pieces with one Q and one H. Inside of that loop, iterate over all the number of half-tile pieces the solution will actually have (from 0 to H, inclusive), replacing half-tile pieces with two Qs:

    int calc2(int Q, int H, int L) {

        int ret = 1000000000;

        // loop over all possible values of H:
        for (int H0=0; H0<=H; H0++) {
            int c = calc1(Q+(H-H0)*2, H0, L);
            if (c < ret) ret = c;
        }

        return ret;   
    }


    int calc3(int Q, int H, int L) {

        int ret = 1000000000;

        // loop over all possible values of L:
        for (int L0=0; L0<=L; L0++) {
            int c = calc2(Q+(L-L0), H+(L-L0), L0);
            if (c < ret) ret = c;
        }

        return ret;   
    }

Reciprocal:

This problem requires you to perform long division the way you learned in elementary school, but with an added twist. Since you must compute digits over 1 billion places from the decimal point, you cannot simply compute them one at a time. The trick is to take advantage of the fact that the digits will eventually fall into a cycle, and to recognize when this happens. This will allow you to jump quickly to the digits you are interested in.

Fractionalization:

This straightforward problem was essentially an implementation exercise. The problem statement basically walked you through the algorithm.

This problem calls for a recursive solution, where at each step you have a call and a fraction m/n. If the current call has p parts, the method finds the largest fraction i/p less than or equal to m/n, and adds the first i parts of the call to the list of calls to return. The test i/p <= m/n can be computed with integer arithmetic as:

i*n <= m*p

(m/n - i/p) * p.

If at any time the method is asked to fractionalize a call that does not have a definition (i.e. an atomic unit) with a fraction other than 0 or 1, the method returns the string "ILLEGAL".

I would like to thank professional square dance caller Bill Ackerman for providing the inspiration for this problem.

GreatExpectations:

Conceptually, this problem requires you to solve for two mutually-dependent sets of data: the expected time for each room, and for each room whether or not you would go through each of the 4 doors given the opportunity. The expectations depend on the decisions you would make for each door, and the decisions you would make for each door depend on the expectations. To solve this problem, we don't need to actually solve for the door decisions -- we can compute them implicitly on the fly.

Let's say we wish to compute the expected time from a room, given the expectations of its four neighbors: A, B, C, and D. Let's assume that these are sorted in ascending order of expectations. Let's also assume for now that we know we will leave this room through any of the four doors, given the opportunity. During any given second, you would choose among the doors that are open and go through the one that leads to the room with the smallest expected time. Thus if door A is open, you would go through it. If door A is closed and B is open, you would go through door B. If doors A and B are closed and C is open, you would go through door C. If doors A, B, and C are closed and D is open, you would go through door D. If all doors are closed, you would wait for the next second and try again.

Given the expectations for the four rooms (eA, eB, eC, and eD) and the probabilities of each of the doors being open at any given second (pA, pB, pC, and pD), the expectation for this room can be computed (with a little algebra) with the equation:

    E =   eA    * pA
        + eB    * pB * (1-pA)
        + eC    * pC * (1-pB) * (1-pA)
        + eD    * pD * (1-pC) * (1-pB) * (1-pA)
        + (E+1)      * (1-pD) * (1-pC) * (1-pB) * (1-pA)

Now, we don't know that it is correct to assume that we would go through any door, even if it were open. Rather than computing this, we can simply loop over all 15 possibilities, modifying the formula above by replacing pA, pB, pC, and/or pD with zero for any door we're considering not going through. From among these 15 possibilities, we select the one that yields the lowest expectation.

To turn this into a complete solution, we initialize the lower-right room with an expectation of 0 and mark its neighbors as "dirty". All other rooms are initialized with a large value representing unreachable. We then repeatedly update the expectation of "dirty" rooms, each time clearing its dirty flag and setting the dirty flag of its neighbors whenever its value decreases. Once there are no more dirty rooms, the expectation of the upper-left room is the final answer.