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 the arrival method above to add this flight to the munimum-bounds list for this airport
4. if it is a departure, follow the steps in departure list, and calculate the minimum frustration required to take this flight
5. iterate over all flights arriving at the proper airport and select the one with minimum frustration

Implementation Notes

• you must use longs. times go up to 10^6, so when squared, this will overflow an int
• doubles should be used for calculation of intersection points
• don't forget to deal with flights that leave from the first airport, they have frustration as well!
• there may be flights which are impossible to take due to, say, not having an incoming flight to that airport before the flight leaves. be sure to handle these gracefully.

import java.util.*;
public class d {
static Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		int n=in.nextInt(),m=in.nextInt();
		long[][] d=new long[m+1][5];// from, to, depart, arrive, min frustration if we take this flight...need to use longs for frustration
		for(int i=1;i<=m;i++)for(int j=0;j<4;j++)d[i][j]=in.nextInt();
		for(int i=1;i<=m;i++)d[i][4]=d[i][0]==1?d[i][2]*d[i][2]:Long.MAX_VALUE;
		TreeSet<Integer> departs=new TreeSet<Integer>(new Comparator<Integer>() {
			public int compare(Integer arg0, Integer arg1) {
				return (int) Math.signum(d[arg0][2]-d[arg1][2]);
			}
		});
		TreeSet<Integer> arrives=new TreeSet<Integer>(new Comparator<Integer>() {
			public int compare(Integer arg0, Integer arg1) {
				return (int)Math.signum(d[arg0][3]-d[arg1][3]);
			}
		});
		for(int i=1;i<=m;i++) {
			arrives.add(i);
			departs.add(i);
		}
		ArrayList<LinkedList<Integer>> lu=new ArrayList<>();
		for(int i=0;i<=n;i++)lu.add(new LinkedList<Integer>());
		while(!arrives.isEmpty()) {
			if (!departs.isEmpty()&&d[departs.first()][2]<d[arrives.first()][3]) {//process departure...pop front off our linked list until it gets worse
				int on=departs.pollFirst();
				int best=Integer.MAX_VALUE;
				while(!lu.get((int) d[on][0]).isEmpty()) {
					int prev=lu.get((int) d[on][0]).pollFirst();
					if(d[prev][4]+(long)Math.pow(d[on][2]-d[prev][3], 2)<=d[on][4]) {
						d[on][4]=d[prev][4]+(long)Math.pow(d[on][2]-d[prev][3], 2);
						best=prev;
					}
					else break;
				}
				if (best<Integer.MAX_VALUE)lu.get((int) d[on][0]).addFirst(best);//add best back to list since could be same for next flight
			} else {//process arrival...use our fancy comparison and pop off the end of the list
				int on=arrives.pollFirst();
				if(d[on][4]==Long.MAX_VALUE)continue;//if we get here with a max value, means there was no valid way to take this flight. don't add.
				while(!lu.get((int) d[on][1]).isEmpty()) {//iterate over back of list...3 cases....
					int next = lu.get((int) d[on][1]).pollLast();
					if (d[on][4]<=d[next][4]+(int)Math.pow(d[on][3]-d[next][3], 2))continue;//if new f is less than curve of n-1, pop...it will never be optimal for future departure
					if (!lu.get((int)d[on][1]).isEmpty()&&intersect(d,on,lu.get((int) d[on][1]).getLast())<intersect(d,next,lu.get((int)d[on][1]).getLast()))continue;//if crossover between new f and n-2 is less than crossover for n-1 and n-2, pop, since n-1 will never be optimal
					lu.get((int) d[on][1]).addLast(next);//don't pop. just push
					break;
				}
				lu.get((int) d[on][1]).addLast(on);//we always go at the end
			}
		}
		long best=Long.MAX_VALUE;
		for(int i=1;i<=m;i++)if(d[i][1]==n&&d[i][4]<best)best=d[i][4];
		System.out.println(best);
	}
	private static double intersect(long[][] d, int on, int last) {//equation is f = (t-d[on][3])^2 + d[on][4]) solve for t. conveniently t^2 drops out, which is why convex hull theorem applies
		return (d[last][3]*d[last][3]+d[last][4]-d[on][3]*d[on][3]-d[on][4])/(2D*d[last][3]-2*d[on][3]);
	}
}