Match Editorial

Match summary

SRM 389 was a relatively easy problem set compared to recent matches. The solution to all of the problems could be coded quite quickly once you figured out the correct algorithm to use, and the constraints were not large enough to present much difficulty. As a result, 90 out of 552 Division One coders completed the hard problem. After the coding phase, Eryx had the high score with almost 1600 points, completing all 3 problems in a total of 24 minutes. However, his 2 successful challenges weren't enough to stop Petr, who overtook him with 125 points in the challenge round. nika finished in third place, with marek.cygan and Mingfei_Li close behind.

In Division Two, Gumx claimed a decisive win in his first SRM, and will be competing in Division One in his next match. Coders d000hg and jjb205 rounded out the top three.

The Problems

Value	250
Submission Rate	623 / 666 (93.54%)
Success Rate	539 / 623 (86.52%)
High Score	samsam for 248.94 points (1 mins 51 secs)
Average Score	214.15 (for 539 correct submissions)

To solve this problem, you simply loop over all of the books and keep track of the weight of the box you are currently filling. If adding the next book would not exceed the weight limit, you add its weight to the total for that box and move on to the next book. On the other hand, if it would exceed the weight limit, you count this box, reset the current weight to the weight of the next book, and continue. Once you are done, don't forget to count the current box even if it is not full. Also, you must be careful to return 0 if there are no books.

    public int boxes(int[] weights, int maxWeight) {
        if (weights.length == 0) return 0;
        int boxes = 0; // number of boxes
        int curr = 0;  // weight of current box
        for (int i=0; i<weights.length; i++) {
            if (curr+weights[i] > maxWeight) {
                boxes++;
                curr=0;
            }
            curr += weights[i];
        }
        boxes++; // last partially-filled box
        return boxes;
    }

545 out of 672 Division Two coders solved this problem correctly. As an interesting exercise, what if you noticed that someone's solution processed the books in the opposite direction, from the bottom of the stack to the top? Can you come up with an input that would cause their program to return the wrong result?

Value	500
Submission Rate	520 / 666 (78.08%)
Success Rate	368 / 520 (70.77%)
High Score	Gumx for 491.41 points (3 mins 46 secs)
Average Score	369.04 (for 368 correct submissions)

Value	250
Submission Rate	544 / 552 (98.55%)
Success Rate	479 / 544 (88.05%)
High Score	ltdtl for 247.42 points (2 mins 54 secs)
Average Score	222.50 (for 479 correct submissions)

The problem statement gave the following identity:

     1      1      c^0     c^1     c^2
    --- = ----- = ----- + ----- + ----- + ...
     b     t-c     t^1     t^2     t^3

From here, you must do three things:

1. compute t
2. compute c
3. evaluate the sum

The problem statement tells you exactly what value to use for t: the smallest power of 2 greater than or equal to b. Starting with the lowest power of 2 (which is 1), continue multiplying it by 2 until it is greater than or equal to b:

    int t = 1;
    while (t < b) t *= 2;

Next, you must compute c. The formula tells you that b=t-c, therefore c=t-b.

    int c = t - b;

Finally, we must compute the first terms terms of the sum. The first term is 1/t, and to compute each additional term, you multiply the previous term by c/t.

    double total = 0;
    double curr = 1.0 / t;
    for (int i=0; i<terms; i++) {
        total += curr;
        curr = curr * (double(c) / double(t));
    } 
    return total * a;

Value	1000
Submission Rate	58 / 666 (8.71%)
Success Rate	15 / 58 (25.86%)
High Score	Gumx for 761.39 points (17 mins 3 secs)
Average Score	457.51 (for 15 correct submissions)

Value	500
Submission Rate	390 / 552 (70.65%)
Success Rate	270 / 390 (69.23%)
High Score	Petr for 433.46 points (11 mins 29 secs)
Average Score	276.08 (for 270 correct submissions)

You can easily show yourself that the result will never be 13 or greater, as this would mean that your fingers are at least 12 frets apart. If they were, you could move your finger on the higher fret down 12 frets and it will still play the same note. Given this fact, you can show that you never need to use the 24th or higher fret, for if you were, you could move every note down 12 frets.

Now, knowing that on each string you only have to consider the first 24 notes it can sound, you can compute how many total possible chords there are. With a maximum of 6 notes in the chord, and each note playable in 2 positions on a given string, there are 12 chord notes on each string, and therefore 12^6 possible chords.

A efficient search can check all of the possible chords, make sure all notes are sounded at least once, and remember the lowest difficulty value seen.

The problem statement gives an example with a difficulty of 4, however higher difficulties are possible. Can you construct an input that results in a higher difficulty value? What is the highest difficulty value possible? (Hint: it's greater than 7.)

Value	1000
Submission Rate	146 / 552 (26.45%)
Success Rate	90 / 146 (61.64%)
High Score	Eryx for 943.79 points (7 mins 0 secs)
Average Score	690.85 (for 90 correct submissions)

Last month in SRM 384, rasto6sk gave us a refresher on using Grundy numbers to solve games that consist of several smaller independent games. This problem was a reward and further practice for those who read and studied this powerful yet quite simple technique. If you had trouble with this problem, you should definitely read his editorial entitled Algorithm Games.

The first step is to decompose the game into a set of smaller games. In this problem, the key is the constraint that says that the top half of each 2x2 block must be in an even-numbered row. This means that we can separate a NxM board into M/2 Nx2 boards. Each of those Nx2 boards is independent -- every block drawn will be in exactly one of those pieces.

The next step is to compute the Grundy number for each state in a single Nx2 board. With a maximum N of 10, there are only 2^20 possible states. To compute a Grundy number, you consider all the states that you can move to (by considering all the places that you can draw a block), and find the smallest Grundy number not represented. This is a perfect task for dynamic programming.

Finally, once you have analyzed all possible states, you compute the logical XOR of the Grundy numbers of the initial states of each of the Nx2 boards. If this XOR is 0 the second player can win the game, otherwise the first player has a winning move.

See the forum for this SRM for some particularly short solutions to this problem.