PROBLEM LINKSDIFFICULTYHARD EXPLANATIONLet x_{i}_{,j} = D_{i}_{,j} + d_{i}_{,j} represents the distance of a direct flight between cities i and j after the modification (there are exactly M such variables). Here D_{i}_{,j} is the original distance between cities i and j and d_{i}_{,j} is the value that Chef will add to the distance. We will represent the shortest path between cities i and j by s_{i}_{,j}. The problem is asking us to minimize sum of d_{i}_{j}. We can formulate this as a linear program (LP) : A straightforward implementation of simplex algorithm is too slow so lets try to find some improvements. The first observation is that simplex tableau is very sparse, which means that you can skip a lot of updates at each iteration of the algorithm. Precomputing some greatest common divisors for the purpose of reducing fractions is a good idea because a lot of time is spent on arithmetic operations with rational numbers. Another trick used by some successful solutions was to run the simplex algorithm with floating point numbers and convert the result to a fraction just before outputting the solution. You can do this by iterating over small denominators until you find a fraction which is close enough to the floating point value. So far we have only mentioned technical optimizations but there is also a more conceptual improvement thanks to our problem tester for this round. We can try to formulate this problem without shortest paths. The only condition that must be fulfilled is that for every simple cycle the length of each edge is no more than sum of other edges. But of course there is a very large number of such cycles. This way we can reduce the number of variables in the linear program, but the number of conditions would increase drastically. The next step was to observe that we need only those cycles for which the only edges between its vertices are the edges of this very cycle. Let's call these cycles "strongly simple". The required condition for all other cycles will be fulfilled automatically. It is hard to estimate the total sum S of lengths of all strongly simple cycles, which is equal to the number of inequalities in our LP problem. It seems that the largest value for S is achieved on the complete graph and equals to N * (N1) * (N2)/2. This LP formulation has approximately the same number of inequalities as our initial solution but only 2*M variables and is fast enough to solve all test cases we could come up with. SETTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 22 Nov '12, 14:20
