Match Editorial

This match seemed relatively uneventful, with the expected quick submissions of SnapDragon (He did reclaim 1st place overall - a "Yay! Back in first!" was seen almost immediately after the match was over and decided). Congratulations to him on an excellent performance, with the highest score on two of the three problems, and the divisions high total score. The Division 1 250 / Division 2 500 was relatively straightforward, but a surprising number of coders in both divisions failed it either during the challenge phage or the system test, due to some hard-to-detect off-by-one errors. To anyone who recognizes and uses DP on a regular basis, the Division 1 650 was probably straightforward - SnapDragon submitted in just under 7 minutes, well ahead of the next coders near the 12 minute mark. The Division 1 900 dealt with string manipulation - not often seen as a Div 1 hard these days, but it was relatively straightforward as well, causing the top coders very little trouble.

Division 2 had a very math-oriented night, as two of the three problems were almost strictly about solving equations. While not extremely complicated, there was enough detail required in the correct formulae that a large percentage of Div 2 coders did not even submit the 1000 pointer, and an equally large percentage of those who did submit it failed in either the challenge phage or the system test.

The Problems

Value	250
Submission Rate	171 / 185 (92.43%)
Success Rate	128 / 171 (74.85%)
High Score	sbh4duke for 243.59 points (4 mins 38 secs)
Average Score	204.89 (for 128 correct submissions)

Overall, a pretty simple math problem. Calculate the sum of the tests and subtract this sum from the total number of tests (including the last test) multiplied by the lowest grade you want (A = 90, B = 80, etc.).

• If the result is less than 0, return 0.
• If the result is greater than 100, it is not possible to achieve the score you want, so return -1.
• Otherwise, round the result up to the nearest integer and return that.

Value	500
Submission Rate	132 / 185 (71.35%)
Success Rate	41 / 132 (31.06%)
High Score	HappyDude for 470.04 points (7 mins 15 secs)
Average Score	325.94 (for 41 correct submissions)

Value	250
Submission Rate	138 / 139 (99.28%)
Success Rate	68 / 138 (49.28%)
High Score	antimatter for 247.21 points (3 mins 1 secs)
Average Score	205.23 (for 68 correct submissions)

There are a couple ways to do this, but the constraints are low enough that a simple loop will from 0 to 1001 suffice:

for i = 0 to 1001
    if the number of background values less than i is less than or equal to 50% of the total number of background values, continue
    for j = 1 to background.length - 3
        if background[j] < i && background[j+1] >= i && background[j+2] >= i && background[j+3] < i then
            continue loop i
    next j
    return i
next i

An alternate way to do this is binary search, but again, the constraints are too low to warrant such effort.

Value	1000
Submission Rate	43 / 185 (23.24%)
Success Rate	10 / 43 (23.26%)
High Score	Billmaan for 898.95 points (9 mins 45 secs)
Average Score	566.18 (for 10 correct submissions)

Here we have what appears to be a relatively simple problem, but is slightly complicated because the lake can change from flooded to normal state within a day (changing the evaporation rate) and vice versa. Even so, this problem requires only a simple loop with some switching logic depending on the day's rain amount and current level.

Because the flood plain is infinitely high, and the lake infinitely deep, it makes sense to use a double (can't use an int because of partial day issues) to represent the level of the lake, with 0 meaning exactly full - the starting state of the lake.

For each day, we need to determine that the change in the lake level will be. The logic for how much the level changes is identical whether flooded or not, with the exception of whether or not we use the flooded evaporation rate or the normal evaporation rate. (That may seem obvious if you recognize this problem as essentially being one function composed of two linear functions). Basically, there are three options for each day:

1. The lake will stay in the same state (although the level may change).
2. The change in lake level is enough to make it reach the boundary between states, but not so much that it actually changes. This happens when the expected change given the current state and rain is greater than the current level and when the rain for the day is between the flooded evaporation rate and the normal evaporation rate. In this case, an equilibrium is reached, and the lake ends up at exactly the full level.
3. The lake will change states. This option requires determining during what fraction of the day the lake will be flooded and during what fraction of the day the lake will be normal - this is what tripped up many coders for this problem.

Value	650
Submission Rate	79 / 139 (56.83%)
Success Rate	67 / 79 (84.81%)
High Score	SnapDragon for 628.28 points (5 mins 19 secs)
Average Score	423.14 (for 67 correct submissions)

While I'm still not the best at programming with DP, I do recognize it fairly readily, and this problem simply screamed DYNAMIC PROGRAMMING at me as soon as I saw it. (As with most DP problems, a recursive approach with memorization also works well). I'll explain the recursive approach here.

Basically, you have a recursive function which takes a from index, a to index, and the array of connect values. Within the recursion, there are a few base cases:

1. If you've calculated this result before, return it as stored.
2. (from == to) - this simply returns 0.
3. (from + 1 == to) - adjacent components. For this, you use the formula given.

Otherwise, you loop from from to to, splitting it into two segments, calculating the minimum cost of all combinations. For instance, if from is 2 and to is 6, you would recurse on ((2,2), (3,6)), ((2,3), (4,6)), ((2,4), (5,6)), and ((2,5), (6,6)). Once the minimum value is calculated, store it somewhere (a two dimensional array works nicely here).

Value	900
Submission Rate	26 / 139 (18.71%)
Success Rate	14 / 26 (53.85%)
High Score	SnapDragon for 635.50 points (20 mins 11 secs)
Average Score	443.05 (for 14 correct submissions)

This problem seems a little tricky at first, and indeed it is. The first thing to do is sort the names alphabetically. The constraints here are small enough to use an iterative approach on the number of rows to use. Basically, just start with 1 row, and increment until you find a solution. Within each trial for a number of rows, iterate over the number of columns to try. Now, within each column iteration, do the following:

• Append the current name to the next row in the output, keeping track of how long the longest one is in the current column.
• At the end of the column, pad each row with enough spaces to make it equivalent to the longest, plus one more for spacing between columns.
• If, at any point in appending names to a row, it becomes wider than the page is, fail and go to the next highest number of rows.
• Once a solution is found, store it if it is the best (determining best by the "rightmost non-space character as far to the left as possible" and "fewest columns" rules).