Thursday, January 24, 2008 Match summarySRM 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 ProblemsBoxesOfBooksUsed as: Division Two  Level One:
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 partiallyfilled 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? ApproximateDivisionUsed as: Division Two  Level Two: Used as: Division One  Level One:
The problem statement gave the following identity: 1 1 c^0 c^1 c^2  =  =  +  +  + ... b tc t^1 t^2 t^3 From here, you must do three things:
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=tc, therefore c=tb. 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;GuitarChords Used as: Division Two  Level Three: Used as: Division One  Level Two:
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.) LittleSquaresUsed as: Division One  Level Three:
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 evennumbered 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. 
