Tuesday, May 1, 2007 Match summary
This transportthemed SRM attracted a good turnout of 1153 competitors. Both divisions were characterized by some low success rates, and an approachable but challenging hard (involving bitmasks in both cases) which only had two successful submissions.
The ProblemsCarBuyerUsed as: Division Two  Level One:
You were asked to find the most economical car over years years. The formula for the total cost of a car over that many years is simply: double dRet = double.MaxValue; for (int i = 0; i < cars.Length; i++) { string[] s = cars[i].Split(' '); dRet = Math.Min(dRet, fuelPrice * annualDistance * years / double.Parse(s[2]) + int.Parse(s[1]) * years + int.Parse(s[0])); } return dRet;Aircraft Used as: Division Two  Level Two: Used as: Division One  Level One:
There were several approaches to this problem, but all of them benefited from some basic transformations which simplified the problem significantly.
I've seen 3 basic approaches to solving this, which I'll outline here: Search for the closest point by using a ternary search The distance between the two aircraft is unimodal over time, so it makes the problem a prime candidate for a ternary search. A ternary search is a great way to find a minimum or maximum of a function that has only one turning point. Start with a full range of potential times that the aircraft would be nearest (Minimum 0, maximum 10^{9} seem like good values). Iterate a suitable number of times to find the time x at which the aircraft were closest. Now we're basically done, right? Wrong. You'll have to calculate the resulting distance at time x using imprecise doubles, and you'll be working with a small error. Considering that there are test cases where the aircraft fly to within 1e11 of the "nearmiss" threshold, working with doubles was very unreliable and could easily have failed on cases tailored to catch out this approach. Thankfully for contestants who used this method (including myself), some of the real killer cases were absent in the system tests and some technically incorrect solutions ended up passing. Solve it using algebra The distance (squared) between the aircraft at time x is (p[0]+x*v[0])^{2} + (p[1]+x*v[1])^{2} + (p[2]+x*v[2])^{2}. We want to know if this expression is ever less than or equal to R^{2}. Expressing this inequality in the form Ax^{2} + Bx + C ≤ 0 gives us: A=v[0]^{2} + v[1]^{2} + v[2]^{2} B=2*(p[0]*v[0] + p[1]*v[1] + p[2]*v[2]) C=p[0]^{2} + p[1]^{2} + p[2]^{2} At this point you will need to know the properties of quadratic graphs to evaluate if there are any nonnegative real roots. As misof's solution very neatly checked with the following 4 lines: if (C <= R*R) return "YES"; if (A == 0) return "NO"; if (B >= 0) return "NO"; if (4*A*C  B*B <= R*R*4*A) return "YES";This approach avoided the precision errors introduced by doubles, but care had to be taken to avoid overflows. In the most extreme cases, B could exceed 2.4 billion, requiring a 64bit data type or unsigned 32bit data type to store it. Solve it using vector geometry Googling for "line point distance topcoder" gave this excellent tutorial by lbackstrom as the first hit. Halfway down the article you'll find the exact code required to evaluate the minimum distance from a vector segment to a point in space. It would be cheating to use this code, and it is only in two dimensional space, but rewriting that code and adapting it to three dimensions would work perfectly to solve the problem quickly and easily (with the same overflow proviso as the algebra method above). TaxiManager Used as: Division Two  Level Three:
This excellent problem tested a wide range of algorithms and abilities. Shortestpath, bitmasks, recursion with memoization or DP. It was really a collection of fairly straightforward subproblems, making it approachable but challenging.
for (int i=0;i<N;i++) for (int j=0;j<N;j++) for (int k=0;k<N;k++) { dis[j,k]=min(dis[j,k],dis[j,i]+dis[i,k]); }I'm simplifying slightly  in other problems you'll have to handle missing paths and negative weight paths differently in the inner loop but for most "roadsbetweenpoints" problems like this it's really that easy. A look at the problem constraints (max 12 customers) suggests that we can use an approach where we represent a set of customers as a bitmask, basically an integer where each binary digit corresponds to a customer. If you haven't used bitmasks, there's an excellent Topcoder tutorial on them here. Using a bitmask customers to represent which customers must still be dropped off, we can define the following recursive relationship (the actual implementation will need memoization to avoid timing out): int HowLong(int customers, int loc) { // Put in memoization, if we've solved this before, return that value if customers==0 return dis[loc,0]; // We're done, go home int best=INF; for each customer in customers { best=min(best, dis[loc,customer.pickup] +dis[customer.pickup,customer.dropoff] +HowLong(customerscustomer,customer.dropoff)); } // Memoize this result return best; }We're almost done! As an added twist, the problem required you to split the load between 2 cars. Now that we're using bitmasks to represent subsets of customers, this is now easy for us to do. Just iterate through every possible set of customers that car A can carry, assign the rest to car B, and the total time taken will be the slower of the 2 cars. int N = customers.Count; int NN=1<<N; int ret=INF; for (int i=0;i<NN;i++) { // Car A is carrying customer set i. // Car B is carrying customer set NN1i. ret=min(ret,max(HowLong(i,0),HowLong(NN1i,0))); } return ret;That's all there is to it. With these 3 really simple steps, you've solved the entire problem. FlightScheduler Used as: Division One  Level Two:
We are asked to find the least fuel that can cover a distance of distance, and this consists of several steps:
flightFuel=emptyMass*(e^{R/K}1) Step 2 is interesting. Most contestants who passed this problem followed their gut feel that the stops must be evenly spaced in order to use fuel most efficiently. For those who are interested, here is an explanation as to why this is the optimal strategy. Consider two consecutive flights covering a total distance of d. The flights have distances of x and dx. totalFuel=2*takeoffFuel + emptyMass*(e^{x/K}+e^{(dx)/K}) Our aim is to minimize this function, so we remove constants which won't alter its shape: totalFuel=e^{x}+e^{dx} To minimize this we need to set its derivative to 0. e^{x}+(1)*e^{dx}=0 e^{x}=e^{dx} x=dx 2x=d x=d/2 Therefore we can minimize the fuel on any two consecutive flights by planning a stop dividing the flight distance exactly in half. We can use this fact to show that any flight plan with unequal flights can be improved by making all the flights the same length. Step 3 is where the majority of the submitted solutions failed. How many stops are required to minimize fuel use? The vast majority of solutions searched from 0 stops up to as many stops as they could calculate in the given 2 second time limit, which seemed to be between 10 and 20 million, depending on implementation. However, there was a test case which required in the region of 63 million stops to use a minimal amount of fuel (200000,1,200000,1), and all of those solutions didn't check high enough, and failed accordingly. Astute contestants who noticed this extreme case cashed in with plenty of challenges, with Masao leading the pack with 9 successful challenges. Various optimizations could alter algorithms to search high enough, but the safest and most reliable was a ternary search from 0 stops to some sufficiently high number of stops. MetroNetwork Used as: Division One  Level Three:
This problem was inspired by a particularly bad day's travel on the London Underground. In fact, residents of London who study example 4 closely may notice that they are mapped on real travel times around Central London, from Gloucester Road to Kings Cross St Pancras in particular!
From this point, we have the option to travel to any other point on the rail network that is connected to this position with lines that are in known. However, we only want to consider useful trips. A trip is useful to us if it does one of 2 things:
double best=INF; for (each i in positions) { if (i is connected to pos via known) { if (i is destination, or i is on an unknown line) { best=min(best,travelTime(pos,i,delayed & ~known)+estTime(i,known,delayed)); } } } return best;We simply return the minimum estimated time of all useful and connected destinations. You'll have noticed the travelTime helper function I referred to earlier. It is important to precalculate all travel times between points based on different states of delay. This is very easy to do by iterating over every delayed bitmask, generating the path lengths along each line, and then using FloydWarshall to fill in the shortest paths. Checking every combination of delayed and known generates too many sets of data, and it's unnecessary. By calling the travelTime function with delayed & ~known we simple ensure that all unknown lines are counted as delayed, and we get a worstcase for the travel time between two points. Calling estTime(start,0,0) returns us the final answer. It almost seems like cheating, considering the complexity of the question. 
