Monday, August 28, 2006 Match summaryDespite featuring some very fast submissions early on, HS SRM 13 was a close challenge to the end. vlad_D, ThomasTuttle, Kalq, duachuotbeo, and LynValente each took a turn in the lead on the strength of quick early submissions. They were overtaken by perennial top finisher tomekkulczynski, who started a bit later but ended up submitting for 1559 points. With many top competitors finished with all problems, the spotlight shifted to Burunduk3, another "red" who had arrived even later and was just starting. At the 56 minute mark, Burunduk3 had just submitted his medium problem and was racing a short clock to finish the hard  and an even shorter clock if he was to edge out tomekkulczynski. He finished, but at the end of coding he trailed tomekkulczynski, LynValente, and Kalq. In the challenge phase, valich identified 4 failed submissions to move into the lead  before losing his own hard solution to a timeout challenge from wintokk. With the system tests eliminating a few more submissions, victory ended up with topseeded tomekkulczynski, followed by wintokk and Burunduk3. The ProblemsWallRepairUsed as: Division One  Level One:
Most competitors scored very well on this problem. There are many ways one could approach this, with no single strategy necessarily the best. One strategy is to loop through the grid and identify holes. Each time you find a hole, check each position above the hole. If you find one or more bricks above the hole, then this hole will need to be filled  so increment your "bricks needed" counter by one. DessertMakerUsed as: Division One  Level Two:
Often the best way to approach a problem is to break it up into parts. In this case, we can break the problem into three independent decisions:
Let's consider each of these decisions for the situation: {"banana", "banana", "ice cream", "chocolate", "chocolate", "peanuts"}Decision #1 We have two "banana"s and two options  we can't have no "banana"s so we will have one or two in our dessert. In general we will have the same number of "banana" options as we have bananas. Conveniently, this holds for the case of 0 "banana"s as well. Decision #2Just like the "banana"s above  but in this case we have only one "ice cream" and thus only one option. Decision #3This is a trickier one. What we really have here is n independent decisions, where n is the number of different other ingredients. For "chocolate" we have 3 options (zero, one or two) and for "peanuts" we have 2 options (zero or one). We multiply these together to get 6 total options for other ingredients. However, one of these options  the option with zero "peanuts" and zero "chocolate"  is invalid as it would leave us with no other ingredients. Thus we're left with 3*21=5 options. Overall decisionSince the 3 decisions are independent, we multiply them out to get 2 * 1 * 5 = 10 total options. The same logics applies in the general case. Let us have B bananas, C icecreams, and k other ingredients (n_{1} units of the first ingredient, ..., n_{k} units of the kth ingredient). The answer will be B * C * ((n_{1} + 1)* ... * (n_{k} + 1)  1). CircuitBoardUsed as: Division One  Level Three:
Many coders got off to a good start on this problem (and a few solved it very fast) but it is not without tricks. Essentially it is a maze problem that needs to be solved a few times. As is often the case with maze problems, a simple solution here is to use a Depth First Search, or DFS. The basic pattern of DFS in a grid maze is something like this: function FindPath(x,y) returns boolean If we are finished the maze at this point, return "true" For each possible next step from here: if FindPath(next step x, next step y)==true, return true We've tried every path and there is no path from here, so return false end function This basic pattern will work for us here  we'll just keep trying to find paths from top to bottom until we can't find a path anymore, and count how many paths we made. However, we'll need to watch out for a few problems: Problem 1: Two data lines cannot use the same cellTo avoid reusing a cell we can mark each cell as "used" if it is involved in a valid path. This is simple to add to our DFS: before each occurence of "return true," we set the current position as "used" or "blocked" to prevent it from being used again. Problem 2: We want to avoid interfering with future pathsWe want to make sure that the line we're drawing does as little as possible to block future lines. In this case, it is sufficient to be "greedy"  we pick the "most left" or "most right" path we can take for each line. To make our DFS greedy, we just have to try each possible starting point in order from left to right, and at each step try paths in left to right order. Problem 3: We are operating under a time limitImagine a large blank grid that is closed at the bottom. Now imagine our algorithm trying every possible path through that grid. There's just too many paths there to consider them all in time. We can drastically cut down on the number of paths we consider by marking each point as "used" or "blocked" if a valid path can't be made from that point to the bottom. This, again, is simple to work into our DFS. What we do is any time we're about to "return false", we set the current point as blocked (as though it was a screwhole). If we can't make a path from that point now, we won't be able to in the future either.
The problem can also be solved using "maxflow" (which was the original intended solution) or using dynamic programming (see tomekkulczynski's solution). If you think of any other approaches, drop a note in the forums.

