Thursday, May 27, 2004 Match summary 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 hardtodetect offbyone 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 mathoriented 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 ProblemsEducationUsed as: Division Two  Level One:
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.).
Used as: Division Two  Level Two: Used as: Division One  Level One:
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
An alternate way to do this is binary search, but again, the constraints are too low to warrant such effort. WaterLevelUsed as: Division Two  Level Three:
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:
Used as: Division One  Level Two:
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:
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). ListerUsed as: Division One  Level Three:
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:

