JOIN
 Match Editorial
SRM 196
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 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

Education
Used as: Division Two - Level One:
 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.

ClapLight
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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.

WaterLevel
Used as: Division Two - Level Three:
 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.
Assemble
Used as: Division One - Level Two:
 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).

Lister
Used as: Division One - Level Three:
 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).
By zoidal
TopCoder Member