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

asdfkajsdf

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);
	}
}