|
Match Editorial |
Tuesday, May 1, 2007
Match summary
This transport-themed 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.
Division 2 was topped by the two coders who managed to crack the hard problem. Long-time member leiz won the division, followed by bgoel1983. First-timer anton_kan had a very impressive debut with good times on the easy, medium and even a couple of challenges - an excellent achievement for a first contest!
In Division 1, kalinov and gawry managed to solve the hard, but a failed medium and a lack of challenges surprisingly left gawry in 9th place. kalinov won the SRM by supplementing his 3 solved problems with 6 successful challenges. He had a very comfortable lead on Revenger and Petr, each of whom solved the easy, medium and had 5 successful challenges.
The Problems
CarBuyer
Used as: Division Two - Level One:
Value 250 Submission Rate 515 / 570 (90.35%) Success Rate 416 / 515 (80.78%) High Score circuit for 248.45 points (2 mins 14 secs) Average Score 193.49 (for 416 correct submissions)
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:
fuelPrice * annualDistance * years / fuelEfficiency (fuel cost)
+ tax * years (tax cost)
+ purchaseCost (purchase cost)
Iterate through all the cars, work out the total cost using the formula, and return the minimum.
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:
Value 500 Submission Rate 251 / 570 (44.04%) Success Rate 29 / 251 (11.55%) High Score MIPT_Alex for 358.82 points (19 mins 30 secs) Average Score 241.91 (for 29 correct submissions)
Value 250 Submission Rate 455 / 527 (86.34%) Success Rate 152 / 455 (33.41%) High Score sluga for 236.55 points (6 mins 51 secs) Average Score 165.53 (for 152 correct submissions)
There were several approaches to this problem, but all of them benefited from some basic transformations which simplified the problem significantly.
- Move the position of the first aircraft to the origin by subtracting p1 from both positions.
- Consider only the velocities relative to the first aircraft by subtracting v1 from both velocity vectors.
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 109 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 1e-11 of the "near-miss" 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 R2.
Expressing this inequality in the form Ax2 + 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 non-negative 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 64-bit data type or unsigned 32-bit 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:
Value 1000 Submission Rate 9 / 570 (1.58%) Success Rate 2 / 9 (22.22%) High Score leiz for 588.16 points (28 mins 21 secs) Average Score 549.70 (for 2 correct submissions)
This excellent problem tested a wide range of algorithms and abilities. Shortest-path, bitmasks, recursion with memoization or DP. It was really a collection of fairly straightforward subproblems, making it approachable but challenging.
Here are the subproblems you needed to solve:
- What is the shortest point between locations i and j?
- How long will it take to deliver a given subset of customers, starting from i and ending at 0?
- What is the best way to distribute the load between two cars?
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 "roads-between-points" 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(customers-customer,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 NN-1-i.
ret=min(ret,max(HowLong(i,0),HowLong(NN-1-i,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:
Value 450 Submission Rate 307 / 527 (58.25%) Success Rate 109 / 307 (35.50%) High Score abikbaev for 430.67 points (6 mins 4 secs) Average Score 249.83 (for 109 correct submissions)
We are asked to find the least fuel that can cover a distance of distance, and this consists of several steps:
- Change the form of the Breguet range equation to express fuel in terms of distance
- Work out an optimal strategy of how to space N stops
- Work out the optimal number of stops
flightFuel=emptyMass*(eR/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 d-x.
totalFuel=2*takeoffFuel + emptyMass*(ex/K+e(d-x)/K)
Our aim is to minimize this function, so we remove constants which won't alter its shape:
totalFuel=ex+ed-x
To minimize this we need to set its derivative to 0.
ex+(-1)*ed-x=0
ex=ed-x
x=d-x
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:
Value 1000 Submission Rate 8 / 527 (1.52%) Success Rate 2 / 8 (25.00%) High Score gawry for 453.43 points (44 mins 46 secs) Average Score 441.51 (for 2 correct submissions)
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!
There were several challenges to overcome in solving this problem. The layout of the input data structured into lines and times made for some interesting parsing code. Additionally, the state at any given time was hard to define clearly. You had a position, you had certain knowledge about the lines (a bitmask seemed suitable), and then there was also the condition of the known lines (another bitmask?).
The relationship between the states was also very unclear. Different states had different types of relationships. If I travelled from position a to position b without gaining any knowledge about the lines, and my travel time was traveltime[a,b], how do I express that as a relationship between those two states?
Well, it's difficult to define problems like this, which makes me love recursion. Build a recursive relationship, ensure that it will never call the same state twice, and we're done. We'll need an important helper function, but we'll get to that afterwards.
(In the next function, known and delayed are bitmasks)
If we're at position pos, we know the state of known lines, and delayed lines are known to be delayed, our estimated time can be defined by the following recursive relationships:
Pos is destination
If pos is destination, we have arrived and can return 0.
Pos is on a line that is not part of known
There are two options. Either line is delayed, or it is not. The probabilities of these two options are 0.01*p and 0.01*(100-p) respectively, so we return the weighted average of the estimated times from those two states.
Return the sum of:
- 0.01*p*estTime(pos,known+line,delayed+line)
- 0.01*(100-p)*estTime(pos,known+line,delayed)
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:
- Gets us to our destination
- Takes us to a line which was previously unknown
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 pre-calculate 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 Floyd-Warshall 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 worst-case 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.
