Match Editorial

Coders in both divisions finished the first two problems in record time. At first glance it appeared this competition would be over before the 30-minute 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 Problems

Value	250
Submission Rate	168 / 178 (94.38%)
Success Rate	166 / 168 (98.81%)
High Score	NeverMore for 249.28 points (1 mins 31 secs)
Average Score	230.21 (for 166 correct submissions)

We first compute the total water volume by looping through the array and summing the durations[i]*rates[i] values (same operation as dot-product). 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;
    }

Value	550
Submission Rate	158 / 178 (88.76%)
Success Rate	67 / 158 (42.41%)
High Score	unclejed for 542.95 points (3 mins 14 secs)
Average Score	424.73 (for 67 correct submissions)

Value	250
Submission Rate	177 / 177 (100.00%)
Success Rate	135 / 177 (76.27%)
High Score	antimatter for 249.53 points (1 mins 14 secs)
Average Score	229.99 (for 135 correct submissions)

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;
   }  
    }

Value	1000
Submission Rate	21 / 178 (11.80%)
Success Rate	6 / 21 (28.57%)
High Score	Chicken1 for 475.97 points (40 mins 56 secs)
Average Score	426.87 (for 6 correct submissions)

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.

Value	500
Submission Rate	151 / 177 (85.31%)
Success Rate	68 / 151 (45.03%)
High Score	dgarthur for 435.02 points (11 mins 19 secs)
Average Score	265.21 (for 68 correct submissions)

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 error-prone than difficult. If only the next was as easy...

Value	1050
Submission Rate	7 / 177 (3.95%)
Success Rate	1 / 7 (14.29%)
High Score	dgarthur for 317.97 points (57 mins 9 secs)
Average Score	317.97 (for 1 correct submission)

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 (depth-first/breadth-first) will run O(n^2). Luckily, based on the constraints, the DP method ran in time.

Now to handle R. The basic idea is to turn the given DFA into another DFA that satisfies the conditions placed on N (pass through exactly R winning positions). To do this we make R copies of the DFA, which could be interpreted as levels. We also add a state D to account for sequences that take paths out of a room that do not exist, or paths that enter more than R winning positions. Each level works as the original map did except, if you enter a winning position, all exiting paths will lead down to the next level. Using this construction we can move all winning positions down to the Rth level, and have a new DFA that satisfies the required constraints. At this point we run the minimization algorithm and have our result. An easy-to-miss step at this point is the removal of unreachable states. If you cannot reach a room in map N there is no reason to include it in a minimal dungeon. The combination of a complicated algorithm, and many tricky twists claimed all but dgarthur's resubmitted solution.