Match summary

Division 1 coders faced a very tricky easy problem, a straightforward medium, and a difficult hard. The result: Many successful challenges and only one correct hard submission. ahyangyi won the match by solving the easy and medium problems, and racking up 5 successful challenges. This victory earned him a place in the Algorithm Top 10. Division 2 also had a high level of difficulty. Newcomer sn0wy0wl won the division and was one of only four coders who solved the hard problem.

The Problems

Trekking

Used as: Division Two - Level One:

Value 250

Submission Rate 595 / 651 (91.40%)

Success Rate 532 / 595 (89.41%)

High Score Torax for 246.86 points (3 mins 12 secs)

Average Score 205.59 (for 532 correct submissions)

This problem can be solved by simply iterating over all given plans and identifying ones that are valid. Out of the valid plans, the one with the fewest camps has to be picked.


for_each_plan P
    if P is valid, result = min(result, number of camps in P)

Pathfinding

Used as: Division Two - Level Two:

Value 500

Submission Rate 224 / 651 (34.41%)

Success Rate 52 / 224 (23.21%)

High Score zouyu9631 for 419.97 points (12 mins 55 secs)

Average Score 243.71 (for 52 correct submissions)

Used as: Division One - Level One:

Value 250

Submission Rate 465 / 595 (78.15%)

Success Rate 238 / 465 (51.18%)

High Score alexilic for 241.38 points (5 mins 24 secs)

Average Score 138.24 (for 238 correct submissions)

A low success rate suggests that this problem is harder than it appears at first glance.

The first thing to notice is that the lower bound for the answer is |x| + |y|, and that the actual answer might only be higher by 2 or 4. That depends on the "general" direction of the given point and the directions of the two lines that it lies on. To be more exact, we need to examine the signs of x and y and their remainder mod 2. This gives us a solution that examines all the 25 possible cases. Noticing that the problem is symmetric with respect to x and y reduces this number to 15. You can keep trying to reduce the different cases and examining them by hand, or use a bfs to calculate the results for all x and y between -2 and 2, which will include all the possible cases.

Another solution to this problem is to walk one step at a time always minimizing the Euclid distance to the desired point (used by wongiseng in his solution).

BikeRiding

Used as: Division Two - Level Three:

Value 1000

Submission Rate 71 / 651 (10.91%)

Success Rate 4 / 71 (5.63%)

High Score ACman for 699.66 points (20 mins 34 secs)

Average Score 633.20 (for 4 correct submissions)

Counting the number of paths in a directed, acyclic graph is a known problem and can be solved using dynamic programming. The "extra" part of this problem is detecting the cycles and checking whether they can be used to produce an arbitrary number of paths from a starting point to the end point. The reference solution used a modified DFS to achieve this.


int count_routes_from_vertex(vertex v)

    if (cached_result[v] <> NULL) then 
        // we've calulated this vertex before
        return cached_result[v]    

    visiting[v] := true

    result := 0

    if (v) is the endPoint then
        result := 1

    for each w in neighbors of v do
        if (visiting[w] = true) then
            // we have just found a cycle
            cycle_start[w] := true

        else result := result + count_paths(w)

    visiting[v] := false
    
    cached_result[v] := result

    return result

To calculate the result using the above function:


result := 0

for each vertex v in startPoints do
    result := result + count_routes_from_vertex(v)


for each vertex v do
    if (cached_result[v] <> NULL and
        cached_result[v] > 0 and
        cycle_start[v] = true) then return -1

return result

In the above code we first sum the results for each path point. However, we must still check whether the answer is not infinite. The if statement in the second loop checks three things, respectively:

whether v is accessible from any starting point
whether the end point is accessible from v
whether there is a cycle passing through v

Notice that if this holds true, there is an infinite number of paths.

The only thing that this pseudocode is missing is the check of overflowing the n value. Checking this in the place of every addition is left as an exercise.

StoneGame

Used as: Division One - Level Two:

Value 500

Submission Rate 397 / 595 (66.72%)

Success Rate 171 / 397 (43.07%)

High Score Burunduk1 for 483.66 points (5 mins 15 secs)

Average Score 347.67 (for 171 correct submissions)

This problem has a simple greedy solution. It assumes the best strategy is:

if you can take a chest in one move (by picking the last stone from it), take the one with the most treasure, else
if possible take any stone that doesn't let your opponent take a chest in one move, else
take any stone

Simulating this behaviour gives a correct solution.

To prove it, let's look at a case where there are no chests with a single stone on top. It's easy to see that if the number of all the stones is odd, the first player takes everything, and if it's even, the second player does. Using the described strategy ensures this result for the winning player. This observation leads to the following: whoever takes the last chest, takes all the chests.

In the general case, we have two groups of chests: ones with a single stone on top, and ones with multiple stones. If we take a stone from one of the chests with multiple stones, the opponent can always react with taking a stone from the same chest, preserving the parity of the stones in the second group (and maybe taking the chest). This proves that you can't change the result for the group of chests with multiple stones if it's not plausible for you. If you are going to get the treasure from the second group anyway, it's also best to take from the first group when possible.

This way, it's always best to try step 1 from the described strategy. When both players do that, the chests with multiple stones always stay until the end, and at that point, the result is known.

ByteLand

Used as: Division One - Level Three:

Value 1000

Submission Rate 20 / 595 (3.36%)

Success Rate 1 / 20 (5.00%)

High Score xhl_kogitsune for 438.63 points (47 mins 44 secs)

Average Score 438.63 (for 1 correct submission)

This problem turned out harder than the author thought it would be.

First, let's reduce this problem to counting the number of new castles needed to preserve a given distance from a city to castle d. This can be done by using a binary search over d.

Next, let's examine a case when the graph is a tree. You can define a recursive function that, for a given subtree, minimizes the number of built new castles, but tries to build them as close as possible to the root. This function will return the number of new castles, the distance to the castle closest to the root, and the distance to the city that is the farthest away from the root and is still not "covered" by a castle. Intuitively speaking, it's a greedy algorithm that builds the castles, but it tries to "pull" them up toward the root, not leaving any "uncovered" vertices behind.

Notice that although the graph is not a tree, it is close. Every connected component is a tree with one additional edge or, from a different perspective, a cycle with one or more trees attached to it.

Having the above function, you can do the following. For each connected component locate its cycle, and try removing each road in the cycle, reducing the component to a tree. The result for this component will be the minimum of the results for the examined trees. This is because having some arrangement of the castles, you can always locate a road such that the cities on its two ends will be "covered" without using this edge. Finally, sum up the results of all components.

For another explanation of the exact same algorithm read Minilek's post.

By rusolis
TopCoder Member