Match Editorial

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.

In division 1, however, the problems were anything but easy. Though most coders made short work of the 250 point problem, they had a hard time with the 600. Many of them submitted some code, but the majority were doomed to failure. The 900 point problem also proved difficult for most, though it had a much higher success rate. When the dust finally settled, SnapDragon and tomek were the only ones to solve all three problems, and SnapDragon ended up with the win. In second place, TAG challenged all 14 medium problems in his room successfully.

The Problems

Value	250
Submission Rate	186 / 201 (92.54%)
Success Rate	178 / 186 (95.70%)
High Score	hsaniva for 246.40 points (3 mins 26 secs)
Average Score	201.83 (for 178 correct submissions)

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.

Value	600
Submission Rate	142 / 201 (70.65%)
Success Rate	120 / 142 (84.51%)
High Score	petra.b1 for 571.08 points (6 mins 27 secs)
Average Score	417.47 (for 120 correct submissions)

Value	250
Submission Rate	177 / 186 (95.16%)
Success Rate	173 / 177 (97.74%)
High Score	antimatter for 247.27 points (2 mins 59 secs)
Average Score	214.60 (for 173 correct submissions)

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.

If you were to assign the strongest unit to a weaker computer unit than the one this algorithm suggests, you could do no better because you would have to put some other unit against the stronger unit that you passed over. Furthermore, if you assigned your strongest unit to a computer unit that defeated it, you would clearly do better by assigning a weaker unit to the computer's unit.

Value	1000
Submission Rate	50 / 201 (24.88%)
Success Rate	38 / 50 (76.00%)
High Score	Esi for 779.35 points (16 mins 5 secs)
Average Score	561.89 (for 38 correct submissions)

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;
    }

Value	600
Submission Rate	126 / 186 (67.74%)
Success Rate	20 / 126 (15.87%)
High Score	jshute for 419.57 points (20 mins 35 secs)
Average Score	266.85 (for 20 correct submissions)

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:
positions = {1,0,2}
angles = {135,45,135}
In this case, cars 0 and 1 collide first, and car 0 blocks car 1. Therefore, cars 0 and 2 both pass all intersections. Many solutions only looked at pairs of cars, and saw that cars 1 and 2 would collide, and since 1 has a lower index, they incorrectly marked car 2 as blocked. There are a number of ways to deal with this case. One way is to look at all triples of cars, and check for this case explicitly. Another way to do it is to look at cars closer together first. The closer cars are together, the earlier they will collide. Therefore, you can look at the adjacent cars first, then the cars with one car between them and so on. You only examine pairs of cars that haven't already been blocked.

Value	900
Submission Rate	56 / 186 (30.11%)
Success Rate	16 / 56 (28.57%)
High Score	SnapDragon for 808.93 points (9 mins 45 secs)
Average Score	566.22 (for 16 correct submissions)

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.

There are a couple of things to watch for. First, you have to be careful of the case where the best solution requires no teleporting. Second, you have to be careful of overflow - snewman got a lot of challenge points on solutions that overflow.

    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[j-1]);
                    long d2 = Math.abs(boxes[k] - boxes[i-1]);
                    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;
    }