|
Match Editorial |
 |
|
||||||||||||||
| |||||||||||||||
| MATCH EDITORIAL LINKS: | |||||||||||||||
|
|||||||||||||||
| |||||||||||||||
June 5, 2002
The Problems
Level One
The Division-I Level One problem seemed more complex than it was necessarily. I don't know of any clever or elegant solution, but it works quite nicely to just try every base dimension up to some limit. John Dethridge picked 40 for the limit on both sides - I don't know where he got the number, but it works. ZorbaTHut just had it go to 1000 on each side. evd had it go to the number of balls, which is more elegant than mine.
In any case, it's a simple brute-force to find the best possibility. Keep track of the "best" - set it to a ludicrous worst to begin with - then try every possibility of base size, up to a point. If it's valid - that is, it can hold enough balls - check if it's better than your current "best". After all the calculations are done, return the best.
This also meant you had to calculate how many balls could be stored given a base, but that's a simple recursive function. You can find an example of it easily in ZorbaTHut's code - it's the function named "calctb".
One thing that tripped several people up was what to do if the new base area matched the current best. Many people didn't notice the instruction to choose the base with the closest-matching sides. You could also achieve the same thing by attempting to minimize the perimeter.
Level Two
The Level Two problem was also rather simple. The easiest way to do it was to first find the smallest funnel that could fit the entire string. It wasn't hard to calculate how many characters could fit in a funnel of a given depth (once again, a recursive calculation was simple), and from there, just make a big character array and fill it from the top. A good way to avoid special cases was to make a 50x50 array and prefill it with spaces. Since x and y were both guaranteed to be between 0 and 49 inclusive, this meant you could just pull the character at that point out and return it - no bounds-checking necessary. I don't know about you, but bounds-checking on diagonal lines isn't my idea of fun.
Some of the calculations are a bit messy, but for the 50x50 array technique I suggest mine, ZorbaTHut's. dmwright's solution is also interesting because it's so different from anything I just mentioned.
Level Three
The Level Three was, in the end, just a simple dynamic programming problem. You took an array of 2^14 items. Each position could be broken down into a bitmask - the bits that are on represent constraints that are not currently satisfied, while the bits that are off represent constraints that are satisfied. Set the entire array to infinity (or a value close enough to it - I used 128) then set the start position - how satisfied each constraint is - to 0. From there, you're just traversing through for each letter. If the letter is in a given constraint, you set the equivalent bit to 1 (since removing it will toggle the correctness of that constraint). Then each position in the array becomes min( current_position, array[ current_position ^ constraint ] + 1 ). At the end you look at position 0, and if it's got a number in it, that's your solution. kv's solution is the cleanest implementation I can find.
