Avoiding Airports

This problem gives us a flight schedule and asks us the cost of the optimal path from one node to another where cost is the sum of squares of the waiting time between arriving and departing at each airport along the path.

Our limits are 200k airports and flights, and all times are within 10^6. This means our runtime has to be mostly linear (+ a log maybe) in one of these.

There are two "obvious" solutions

Dijkstra

If we connect flights to other flights with edges only if they arrive at the same airport with a weight of the square between the arrival/departure time, then we can simply run dijkstra across this modified graph, and it WILL produce the answer.

The runtime, however, is dominated by e, which in the worst case is 200k^2 in the modified graph (every flight takes you back to the same airport).

DP

The classic DP solution encodes its subproblem as minimum frustration to be at airport A at time T. Then for a given A,T pair, we can either take the flight that arrives at the airport at that time (should one exist), or iterate over all previous T at the airport, and choose the arrival T which would give us minimum frustration at this T.

This of course yields n^3 runtime, which is way too slow.

DP Optimizations

Interesting Points/Dimension Elimination

The first thing to notice is that time is redundant with flight. We don't need to analyze all T at every airport. We only need to lookup frustration for a given T if a flight is arriving or departing from that airport. This is means our table only has 2*flights total entries. You'll note that by only examining flights, instead of all time, we've eliminated time as a dimension altogether! The rules above still apply. Analyze all prior arrival times at a given airport and choose the one that yields the minimum cost for this departure time.

This yields a runtime of n^2.

Convex Hull Optimization

(hint: the use of the n^2 as the cost function is a dead giveaway that this is the optimization. Buffed Buffet has the exact same pattern)

If one writes the frustration function for a given flight arrival (the frustration t time after the arrival), it is something like

frustration = (t-arrival)^2 + arrival_frustration = t^2 - 2*arrival*t + arrival^2 + arrival_frustration

This means that every flight is a parabola of shape t^2, as you would expect. From this, we can conclude that any two functions of that form have exactly one intersection point, or more topically, for any two flights arriving at a given airport, there is a single departure time at which it would be equally optimal to take either arriving flight. If our departure time is previous to that time, one flight will always be optimal, and if later, the other.

Written a different way, suppose we have two flights arriving at the airport at times a and a', with frustrations b and b'. given the above described curve, frustration = f(t,arrival,arrival_frustration), there is some time t for which f(t,a,b) == f(t,a',b'). If a flight departs with time less than t, if f(t,a,b) < f(t,a',b'), it will be optimal for ALL time less than t. The rule applies when the signs are changed as well.

This means if we maintain a list of ranges of departure times for which a given arriving flight is optimal, we can simply perform a lookup instead of iterating over all arriving flights.

The way we do this in linear time involves one other corollary

• If a given incoming flight is determined to be optimal for a given outgoing flight, no prior incoming flights will ever be optimal in the future
  • One can prove this by demonstrating that the function for later incoming flight is lower in value and has a lesser slope, and thus will always be less than the prior flights

We can use this fact to come up with the following algorithms (assuming arrivals and departures are examined in increasing t) Arrivals: The goal here is to come up with minimum bound of the graph of all the flights frustration functions. Thus when a new flight is added, since we are going in increasing t, there is some time in the future at which it WILL be optimal, we have to figure out, though, if some other flight is no longer optimal ever.

1. If the arrival flight is below the curve of the previous flight which would be optimal at the arrival time, the previous flight will never be optimal in the future, and can be discarded (see the corollary)
2. If the above does not apply, there is still a situation where the previous flight is not optimal...when the crossover from the n-2 flight to the new flight occurs EARLIER than the crossover from the n-2 flight to the n-1 flight. Here we compare the intersection times of the two. If we pass directly from the n-2 curve onto the new curve, then then the n-1 curve will never be optimal
3. repeat the above process until no curve is discarded, then add the new curve to the end of the list

Departures: We have to walk the list to find the optimal incoming flight to take

1. examine the first incoming flight in our minimum-bound list, built as described above
2. examine the SECOND flight on the list.
3. if the second flight is better than the first, discard the first, as per the corollary
4. else, break, since we know all further curves can't be optimal since we haven't hit their crossover points yet (and if we had, this flight would have been discarded as never having been optimal!

Runtime

We know the following things happen for each flight exactly once:

1. We process it's arrival
2. we process it's departure
3. we ADD it to the minimum-bounds list of some airport
4. we REMOVE it from the minimum-bounds list of some airport

All the operations involved in building the list as described above result in either the addition or removal of SOME flight from the list (either ourselves or someone else). Since we know that these things only happen once per flight, the total runtime is linear for this part.

Convex Hull Optimization?

You may ask why we call this the convex hull optimization, despite the fact that we are really finding the minimum bound of a set of parabolas, which is decidedly non-convex. Since every function has a t^2 term in it, we can subtract that off. Which yields the following function which is linear in t, while having the same intersection points:

modified_frustration = - 2*arrival*t + arrival^2 + arrival_frustration

Since arrival is increasing, by our choice of how to process, we know that the slope of the line is DECREASING. If we were to graph all the lines, the area of interest would be the convex hull of the area enclosed by all the lines and the origin.

Full algorithm

1. add all arrivals and departures to their own lists sorted by time.
2. select the next event, regardless of type
3. if it is an arrival, follow

import java.util.*;
public class a {
	static Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		int n=in.nextInt();
		StringBuilder ans=new StringBuilder(String.format("%d:\n",n));
		for(int i=2;i<n;i++) {
			if(n%(i+i-1)==0||(n-i)%(i+i-1)==0)ans.append(String.format("%d,%d\n", i,i-1));
			if(n%i==0)ans.append(String.format("%d,%d\n", i,i));
		}
		System.out.print(ans);
	}
}