PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
Let xi,j = Di,j + di,j represents the distance of a direct flight between cities i and j after the modification (there are exactly M such variables). Here Di,j is the original distance between cities i and j and di,j is the value that Chef will add to the distance. We will represent the shortest path between cities i and j by si,j. The problem is asking us to minimize sum of |dij|. We can formulate this as a linear program (LP) :
for all i, j, k such that there is a direct flight between cities i and k
si,j <= (Di,k + di,k) + sk,j (conditions for shortest paths)
for all i, j such that there is a direct flight between cities i and j
(Di,j + di,j) <= si,j (direct connection should be the shortest path)
minimize sum(|di,j|)
It is never optimal to reduce distances below 1 so we don’t have to worry about the restriction that the distances should be positive. The standard method to get rid of absolute values |di,j| in a linear program is to represent the modification di,j as a difference of two positive variables di,j
+ - di,j-. The expression which we’re trying to minimize changes to sum(di,j
+ + di,j-). We have a valid linear program but most linear programming algorithms require a valid initial solution and things become much more manageable if setting all variables to 0 gives this initial solution. Note that setting all flight distances to 0 gives a valid solution so we can shift the linear program by Di,j in every dimension. This brings us to a linear program which can be solved by simplex algorithm. The problem with this solution is that it is hard to tell whether it will be fast enough or not until you actually try it out and is not trivial to code it. That’s probably one of the reasons for the low number of attempted solutions.
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 * (N-1) * (N-2)/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 SOLUTION
Can be found here.