Wednesday, May 5, 2004 Match summary Coders in both divisions finished the first two problems in record time. At first glance it appeared this competition would be over before the 30minute mark. These thoughts were quickly dismissed as players' read their respective hards. Div 1 coders faced a complex problem in automata theory that was both difficult conceptually, and tricky to implement. Div 2 coders faced a deceptively easy simulation, whose nuances claimed most solutions. As Div 1 coders raced to complete the set, SnapDragon and dgarthur traded compile and test cycles. SnapDragon's solution was plagued with a bug he couldn't find in time. dgarthur submitted earlier than everyone, but found himself resubmitting later. Seven coders marched into the challenge round with their level 3 problems intact. Only dgarthur's remained when the dust cleared. Division 2 had a similarly deadly challenge phase/systest phase. In the end Flyboy216 emerged victorious, with DAle close behind.
The ProblemsSwimmingPoolUsed as: Division Two  Level One:
We first compute the total water volume by looping through the array and summing the durations[i]*rates[i] values (same operation as dotproduct). The result is the total water volume, so we divide by the given height to get the answer. Java code follows: public int area(int[] rates, int[] durations, int height) { int water = 0; for (int i = 0; i < rates.length; i++) water +=rates[i]*durations[i]; return water/height; }CRTFun Used as: Division Two  Level Two: Used as: Division One  Level One:
CRTFun is based on the Chinese Remainder Theorem (CRT) used in modular arithmetic. Given a system of congruences (equations) that satisfy certain constraints, the CRT tells us there will be a unique solution within certain bounds. Coders were required to find that solution. Luckily additional artificial bounds were guaranteed by the constraints, so a brute force method would be applicable. Simply loop up to 100000, testing each value along the way. If one satisfies all given congruences, you have the solution. Java code follows: public int findSolution(int[] mods, int[] vals) { outer: for (int i = 0; ;i++) { for (int j = 0; j < vals.length; j++) if ( i % mods[j] != vals[j] ) continue outer; return i; } }ConquerMap Used as: Division Two  Level Three:
Not much can be said about ConquerMap. Basically a pure simulation problem. You have an initially blank board, and a rule that allows it to mutate from one turn to another. Mutations include the introduction of new numerals, or the movement of old numerals. An outer loop iterates through time, while inner loops generate a new board from the old one. A bit of care is required to make sure the correct spaces are considered during potential conflict situations. Other potential issues include the handling of boundary cases, and properly computing which numeral wins each conflict. Pitfalls such as these claimed numerous submissions. ShortBooleanExpUsed as: Division One  Level Two:
ShortBooleanExp brings back memories of junior high school, when math amounted to filling in a truth table. One way to solve this problem involved enumerating all possible strings until you found one that agreed with the given expression. To see if two expressions agree, simply try all possible truth combinations for a and b. This is akin to checking if their columns on a truth table would match up. A faster way involves filling an array with precalculated solutions. Simply search this array to find the correct answer instead of the slower enumeration process. One way or another, many coders zipped through this problem. Those taking the latter path often zipped into a successful challenge. All things considered though, this problem was more careless errorprone than difficult. If only the next was as easy... DungeonBuilderUsed as: Division One  Level Three:
DungeonBuilder erases all memories of junior high school, and reminds
me why college can be evil. This problem comes right out of automata
theory. The input sequences used by the players, are really just
strings of digits. The dungeons are really just Deterministic Finite
Automata (DFA), where each room is a state.
If there was no R value, this problem would come down
to implementing the standard DFA minimization algorithm. Effectively the
minimization algorithm marks off which states could be merged
together in order to make a simpler, smaller machine. As a base
case, any pair of states such that one is a winning position, and the
other isn't can be eliminated from merging consideration. For the
inductive case, assume you knew two states p and q could not be
merged. If you have two other states r and s such that r can reach p
on some letter c, and s can reach q on c, then r and s cannot be
merged either. Dynamic programming is a popular way to implement this
process, but it has a worst case runtime of O(n^3). A DFS/BFS based
solution (depthfirst/breadthfirst) will run O(n^2). Luckily, based
on the constraints, the DP method ran in time. 
