Match Editorials

Match summary

Despite 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 top-seeded tomekkulczynski, followed by wintokk and Burunduk3.

The Problems

Value	250
Submission Rate	93 / 96 (96.88%)
Success Rate	92 / 93 (98.92%)
High Score	vlad_D for 248.82 points (1 mins 57 secs)
Average Score	229.00 (for 92 correct submissions)

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.

Value	500
Submission Rate	60 / 96 (62.50%)
Success Rate	54 / 60 (90.00%)
High Score	tomekkulczynski for 482.80 points (5 mins 24 secs)
Average Score	326.87 (for 54 correct submissions)

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:

1. How many "banana"s will be used?
2. How many "ice cream"s will be used?
3. Which other ingredients will be used?

Let's consider each of these decisions for the situation:

    {"banana", "banana", "ice cream", "chocolate", "chocolate", "peanuts"}

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.

Just like the "banana"s above - but in this case we have only one "ice cream" and thus only one option.

This 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*2-1=5 options.

Since 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 ice-creams, and k other ingredients (n₁ units of the first ingredient, ..., n_k units of the k-th ingredient). The answer will be B * C * ((n₁ + 1)* ... * (n_k + 1) - 1).

Value	1000
Submission Rate	43 / 96 (44.79%)
Success Rate	14 / 43 (32.56%)
High Score	tomekkulczynski for 827.59 points (13 mins 33 secs)
Average Score	575.48 (for 14 correct submissions)

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:

To avoid re-using 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.

We 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.

Imagine 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 "max-flow" (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.