Match summary

tomekkulczynski took first place in this match, thanks to seven successful challenges. He was followed by Zuza, in second place, with fatit close behind in third.

The 500 problem was the most frequently challenged, probably because of several tricky corner cases. Less than one third of all medium submissions survived the challenge phase and the system tests. The 1000 problem was rather standard for High School SRMs and 17 people managed to solve it.

The Problems

ApplePie

Used as: Division One - Level One:

Value 250

Submission Rate 148 / 157 (94.27%)

Success Rate 130 / 148 (87.84%)

High Score sluga for 249.22 points (1 mins 36 secs)

Average Score 230.82 (for 130 correct submissions)

The solution to this problem is straightforward: Iterate over all apples in the order in which they are given, counting the ones that fall within the given rectangle. If the counter equals the amount that we need, return the day on which the current apple fell.

This approach (or similar) was used in sluga's solution.

FrogDerby

Used as: Division One - Level Two:

Value 500

Submission Rate 97 / 157 (61.78%)

Success Rate 30 / 97 (30.93%)

High Score crazzy for 467.72 points (7 mins 34 secs)

Average Score 300.03 (for 30 correct submissions)

For this problem, let's call points (x[i],y[i]) and (x[j],y[j]) co-linear if x[i]/y[i] = x[j]/y[j] or y[i]=y[j]=0. It can be proven that using a jump with coordinates (x[i]/d, y[i]/d) (where d=gcd(x[i],y[i])) you can visit all points that are co-linear with (x[i],y[i]) and are on the same side of x-axis and y-axis. Thanks to this, the algorithm can be as follows:

for each point p do

    count the points that are co-linear with p and on the same side of x-axis and y-axis.

return the maximum result

The easiest way to see if points (x[i],y[i]) and (x[j],y[j]) are co-linear is to check if x[i]*y[j] = x[j]*y[i] or y[j]=y[i]=0

Correctly handling zero and negative coordinates was very important in this problem.

For a reference, see TICKET_112022's solution.

WarehouseJob

Used as: Division One - Level Three:

Value 1000

Submission Rate 27 / 157 (17.20%)

Success Rate 15 / 27 (55.56%)

High Score sluga for 864.26 points (11 mins 38 secs)

Average Score 632.55 (for 15 correct submissions)

This problem has a standard backtracking solution. Let's look at the recursive version. Let rec be a function that, given a subset of boxes, calculates the cost of the cheapest arrangement using these boxes.

n = total number of boxes;

int rec(boxes){
    height = n - size of boxes;
    cost= infinity;
    for each b in boxes do {
        if some box in boxes must lie under b, go to next box;
        c= rec(boxes - b);          //boxes-b is a set operation
        cost = min(cost, c + weight(b)*height);
    }
    return cost;
}

The above function counts the cost of the optimal arrangement. To make it a valid solution, we need to add two things. First, it must also return the box at the bottom of the arrangement, so we can retrace the order:

n = total number of boxes;

(int,box) rec(boxes){
    height = n - size of boxes;
    cost= infinity;
    for each b in boxes do {
        if some box in boxes must lie under b, go to next box;
        c=(first value of) rec(boxes - b);
        if cost < c + weight(b)*height {
            cost = c + weight(b)*height;
            best_box=b;
        }
    }
    return (cost,best_box);
}

retrace(boxes){
    for i=1 to n do {
        b=(second value of)rec(boxes);
        boxes:=boxes-b;
        b is the i-th box from the bottom;
    }
}

It's easy to see that if the loop in rec traverses the boxes in increasing order, then retrace calculates the lexicographically smallest arrangement (out of all optimal arrangements).

The second thing to add is memoization, which is left as an exercise for the reader (it's basically adding a table of size 2ⁿ and changing the first and last line of rec).

By rusolis
TopCoder Member