Match Editorial

About 15 minutes into the competition, both SnapDragon and tomek had submitted the easy and medium, with SnapDragon leading by only 17 hundredths of a point. However, by submitting the level 3 in under 14 minutes, tomek pulled ahead and ended up winning the division. With his second challenge win, tomek pushed his rating up to become the second highest rated coder. The problem set provided some interesting stats, with some of the highest success rates among submissions that I've seen in a while. In Division 1 alone, over 80% of all problems submitted passed system tests. In Division 2, newcomers EugeneY and iforiq took the first and second spots. A good mix of topics, the problems covered simulation, geometry, combinatorics, and of course, brute force.

The Problems

Value	250
Submission Rate	155 / 188 (82.45%)
Success Rate	120 / 155 (77.42%)
High Score	sh_maestro for 247.72 points (2 mins 43 secs)
Average Score	202.09 (for 120 correct submissions)

There is a very straightforward solution to this problem which involves knowing the greatest common denominator (gcd) formula. Fortunately, this was a division 2 easy, so brute force also works. Simply start at 1 and increment until you get a number which is divisible by all the numbers in the range. To check if a number is divisible, use the mod operator (% in Java, C++, and C#, Mod in Visual Basic .net). If a % b = 0, then a is divisible by b. Since 1-12 was the worst case, and the answer was only 27720, the worst case only does 12 * 27720 operations.

If you know gcd, then the lcm of two numbers is simply:

a / gcd(a, b) * b

The lcm of a sequence of numbers is:

lcm(a₀, lcm(a₁, ... lcm(a_n-1, a_n)...))

so the code can be written:

int ret = first;
for(int i = first; i <= last; i++)
  ret = ret / gcd(ret, i) * i;
return ret;

Value	500
Submission Rate	137 / 188 (72.87%)
Success Rate	75 / 137 (54.74%)
High Score	EugeneY for 470.44 points (7 mins 12 secs)
Average Score	327.50 (for 75 correct submissions)

Value	250
Submission Rate	137 / 143 (95.80%)
Success Rate	122 / 137 (89.05%)
High Score	sjelkjd for 248.54 points (2 mins 10 secs)
Average Score	213.92 (for 122 correct submissions)

I think I remember Mr. Wizard proving that you can't fold a paper more than 8 times. In any case, this problem is solved with a simple brute force algorithm. Since folding the paper in one direction is independent of folding it in another direction, it makes sense to consider both directions independently. Also, since you can rotate 90 degrees, you should try fitting each dimension of the paper in each dimension of the box. If the number of folds required for either orientation exceeds 8, then that orientation is invalid. If neither is valid, return -1, otherwise, return the minimum of the valid ones.

I saw three approaches to representing the numbers in this problem. First, and easiest, was with doubles. Since we are only ever dividing by 2, doubles can accurately represent the numbers with no problems. The second is by multiplying everything by 2⁸. Since you will only ever divide any value 8 times, the precision will be there. The final, and probably most creative method (as seen in sjelkjd's solution), is to multiply the box by 2 instead of dividing the paper by 2 for each fold.

Value	1000
Submission Rate	23 / 188 (12.23%)
Success Rate	22 / 23 (95.65%)
High Score	PadawanLearner for 707.89 points (20 mins 4 secs)
Average Score	527.14 (for 22 correct submissions)

This problem was a straightforward simulation. To solve it, you must keep track of which masters have transmitted their messages, which masters still need to transmit their messages, and which masters are currently transmitting their messages. When the bus is free, each master that has not yet transmitted tries to transmit. For each byte transmitted, you must first check for the slowest master currently transmitting the byte, and add its transmission time to the total time. Then, check to see the lowest byte transmitted. Finally, any masters that did not transmit the lowest byte should lose their currently transmitting status. The message is over when one master reaches the end of its transmission. At this point, all masters who have not transmitted their messages should retry transmitting. The simulation ends when all masters have transmitted their messages.

Value	500
Submission Rate	83 / 143 (58.04%)
Success Rate	69 / 83 (83.13%)
High Score	tomek for 440.69 points (10 mins 43 secs)
Average Score	296.67 (for 69 correct submissions)

Inspired by trying to fit too many jars into my refrigerator, this problem involves some fundamental geometry and some looping.

First, we must establish how to calculate the width of a box that holds jars. It becomes quite clear from looking at the examples that there are two possibilities. One where all the odd rows have one more jar than the even rows, and one where both the even and odd rows have the same number of jars. In the first case the width is just enough to fit the odd rows of jars. In the second case, the width is enough to hold the odd rows of jars, plus one more radius to hold the even rows, since the rows are skewed by one radius.

Second, we must establish how to calculate the length. This is where the geometry comes in. Since a jar in row n is touching two jars in row n-1, and the two jars in row n-1 are both touching each other, it is clear that the distance between the centers of any two of these jars is 2*radius, or 2r. We can form a triangle between the three centers, and since all sides of this triangle are equal, we have an equilateral triangle. If we split the triangle in half down the center, we have two right triangles, with a width of r, and a hypotenuse of 2r (see diagram). If we use the pythagorean theorem, we can calculate the length:

r2 + L2 = (2r)2
L2 = 4r2 - r2
L2 = 3r2
L = sqrt(3) * r.

This means that the center of each row is sqrt(3) * r away from the center of the previous row. So the length of a box will be:

r + sqrt(3) * r * (rows-1) + r

The two r's on the ends are for the distance from the bottom of the box to the center of the first row, and the distance from the center of the last row to the top of the box.

Once the math is done, we can iterate through all the possible widths (one radius at a time) and fit as many rows as possible into the resulting height. We then take the maximum of these values.

Value	1000
Submission Rate	27 / 143 (18.88%)
Success Rate	22 / 27 (81.48%)
High Score	NGBronson for 866.05 points (11 mins 32 secs)
Average Score	629.30 (for 22 correct submissions)

The name of this problem, although it is never really mentioned in the problem statement, is a big clue on how to solve it. Basically, you need to calculate all the permutations that are lexicographically smaller than the given permutation. However, using a function like next_permutation isn't going to help because there are just too many permutations to loop through. So we need to establish a way to calculate the number of permutations up to a certain point quickly.

First, we define the choice function as the number of ways to choose exactly n locations out of m possible locations. There is a nice closed formula for this:

C(n,m) = m!/((m-n)! * n!)

However, these numbers can get very large, even if the result of the formula is very small. There is also a recursive way to define the choice function, which will guarantee that the largest number you calculate is the answer. However, if you use this method, you should use some kind of memoization to avoid timeouts. The recursive relationship is:

C(0,m) = 1
C(n,0) = 0
C(n,m) = C(n-1, m-1) + C(n,m-1)

Now, we can calculate the number of permutations that are less than a given number. Let's say that we have the number 20012011211. The most significant digit of this number is the 2 at the front. There are a certain number of ways to arrange this group of digits. Some of them are below the current arrangement lexicographically, and some are above. We know that at least all the arrangements that start with a digit lower than '2' are below. If we use a '1' as the first digit, we have four 1's and three 2's left to arrange. This can be done by picking all possible places for each of the digits. First we count all the ways to choose 4 locations out of the 10 remaining for the '1' digits. Then we count all the ways to choose 3 locations out of the remaining 6 for the '2' digits. The result is:

C(4,10) * C(3,6).

Next, we know that all permutations that are less than 11 digits long (i.e. start with a '0') are less than the current permutation. So we choose 5 out of 10 locations for the '1' digits, and 3 out of 5 locations for the '2' digits. The result is:

C(5,10) * C(3,5).

Once we have exhausted all the digits lower than the original first digit, there is no nice formula to use, but we can simply move on to the next non-zero digit and repeat the process. So the number of permutations less than 20012011211 is the number of permutations of this number which start with 0 or 1 plus the number of permutations of 12011211 that are less than that number.