Monday, October 30, 2006 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 ProblemsApplePieUsed as: Division One - Level One:
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. FrogDerbyUsed as: Division One - Level Two:
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 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. WarehouseJobUsed as: Division One - Level Three:
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 2n and changing the first and last line of rec). |
|