Wednesday, October 27, 2004 Match summary
SRM 217 was pretty easy on division 2, with many coders solving the first two
problems. haipt81 ended up winning without any challenges by less than 3
points. Esi was a close second, followed by nihilista, almost 80 points behind.
The ProblemsFuelConsumptionUsed as: Division Two  Level One:
This problem was pretty straightforward. If your car is going at x kilometers per hour, and uses y liters of fuel per hour, then at can go x kilometers on y liters of fuel. Therefore, if you have fuel liters of fuel, you can go x*fuel/y kilometers. You should calculate this value for each potential speed, and return the maximum. PlayGameUsed as: Division Two  Level Two: Used as: Division One  Level One:
The first thing you should do in this problem is sort each input. Next,
consider your strongest unit. You should put this unit up against the strongest
unit that it can defeat. That way, your unit wins, and it defeats a strong unit
of the computer. You then move on to the next strongest unit, and so on.
Used as: Division Two  Level Three:
Consider a pair of cars, a and b, with a starting to the left of b. If the angle of a is less than the angle of b, their paths will eventually intersect. But, which of the two cars will get their first? The car with the angle closer to 90 degrees will always get to the intersection first. What happens if a or b is blocked before it gets to the intersection. It turns out that it doesn't matter because if a would block b, and another car c would block a, then c will also block b. The only exception to these rules is the case where there are ties. If two cars reach the intersection at the same point because there angles are equidistant from 90, then the one with the lower index wins. public int[] getOut(int[] angles){ int[] r = new int[50]; int ptr = 0; loop:for(int i = 0; i<angles.length; i++){ for(int j = 0; j<angles.length; j++){ if(j<i && angles[j] < angles[i] && Math.abs(angles[j]90) <= Math.abs(angles[i]90)) continue loop; if(j>i && angles[j] > angles[i] && Math.abs(angles[j]90) < Math.abs(angles[i]90)) continue loop; } r[ptr++] = i; } int[] ret = new int[ptr]; System.arraycopy(r,0,ret,0,ptr); return ret; }Crossings Used as: Division One  Level Two:
This problem was very similar to the division 2 hard. The difference was that
the positions of the cars were part of the input. As in the division 2 hard,
only the order mattered, but because of the way ties are broken (by index),
there were a couple of tricky cases that cause most solutions to fail. The
trickiest one was something like: Used as: Division One  Level Three:
Dynamic programming is always tough, and this problem was no exception. First
off, you should notice that there is no reason to teleport any boxes to a floor
that none of them are going to. If you did, and x boxes had to be
moved up, and y boxes had to be moved down, and x >
y, then by teleporting the boxes one floor higher, your cost would be
lower. Similarly, if y > x, then it would be better to
teleport one floor lower, while if they are equal, we can teleport one floor
lower or one floor higher, and the cost is the same. From here there are a
number of different ways to proceed. I used dynamic programming to find the
cost of a solution, cost[i], where the highest floor to which boxes
were teleported was i, for each i. Given
cost[j], with j<i, we can calculate the cost of
the solution whose two highest teleports are i and j. The
boxes going to floors below j are still teleported to the same place,
as it would never make sense to teleport them to i over j.
Each of the boxes above j was teleported to j in the
solution giving cost[j] and from j they were moved up,
so we know exactly how much it cost to move each of those boxes. Therefore, we
can subtract thoses costs from cost[j]. This gives us the cost of
transferring all the boxes going to j or below. Finally, we
teleport each of the boxes going to floors above j to either j
or i, whichever is closer, and add up the cost. This gives us the
minimum cost of a solution whose two highest teleports are i and
j. Minimizing this over all j, we get cost[i].
Finally, we return the minimum cost[i] over all i. public int cheapTransportation(int[] boxes, int tc, int lc){ Arrays.sort(boxes); long[] cost = new long[boxes.length+1]; for(int j = 0; j<boxes.length; j++){ cost[0]+=boxes[j]*lc; } //cost[0] is the cost with no teleporting long ret = cost[0]; for(int i = 1; i<cost.length; i++){ long min = 1000000000000000000L; for(int j = 0; j<i; j++){ //add tc to cost[j] to account for //the teleportation to i long tmp = cost[j]+tc; for(int k = 0; k<boxes.length ;k++){ //d1*lc is the cost for box k if we teleport //it to j, while d2*lc corresponds to sending k to i long d1 = boxes[k]  (j==0?0:boxes[j1]); long d2 = Math.abs(boxes[k]  boxes[i1]); tmp = d1*lc; tmp += Math.min(d1,d2)*lc; } //tmp is the cost where i and j are //the two highest teleports min = Math.min(min,tmp); } ret = Math.min(ret,min); cost[i] = min; } return (int)ret; } 
