USACO 2020 January Contest, Platinum Problem 3. Falling Portals

USACO 2020 January Contest, Platinum Problem 3. Falling Portals

There are NN (2N21052≤N≤2⋅105) worlds, each with a portal. Initially, world ii (for 1iN1≤i≤N) is at xx-coordinate ii, and yy-coordinate AiAi (1Ai1091≤Ai≤109). There is also a cow on each world. At time 00, all yy-coordinates are distinct and the worlds start falling: world ii moves continuously in the negative-yy direction at a speed of ii units per second.

At any time when two worlds are at the same yy-coordinate (possibly a fractional time), the portals "align", meaning that a cow on one of the worlds can choose to travel instantaneously to the other world.

For each ii, the cow on world ii wants to travel to world QiQi (QiiQi≠i). Help each cow determine how long her journey will take, if she travels optimally.

Each query output should be a fraction a/ba/b where aa and bb are positive and relatively prime integers, or 1−1 if it the journey is impossible.

 

SCORING:

 

  • Test cases 2-3 satisfy N100.N≤100.
  • Test cases 4-5 satisfy N2000.N≤2000.
  • Test cases 6-14 satisfy no additional constraints.

 

 

INPUT FORMAT (file falling.in):

The first line of input contains a single integer N.N.The next line contains NN space-separated integers A1,A2,,AN.A1,A2,…,AN.

The next line contains NN space-separated integers Q1,Q2,,QN.Q1,Q2,…,QN.

 

OUTPUT FORMAT (file falling.out):

Print NN lines, the ii-th of which contains the journey length for cow i.i.

 

SAMPLE INPUT:

4
3 5 10 2
3 3 2 1

SAMPLE OUTPUT:

7/2
7/2
5/1
-1

Consider the answer for the cow originally on world 2. At time 22 worlds 1 and 2 align, so the cow can travel to world 1. At time 7272 worlds 1 and 3 align, so the cow can travel to world 3.

 

Problem credits: Dhruv Rohatgi

<h3>USACO 2020 January Contest, Platinum Problem 3. Falling Portals 题解(翰林国际教育提供,仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

Fix i.i. Consider a graph of time versus yy-coordinate; then world ii is represented by a line of slope i−i. Call a point (T,Y)(T,Y) on this graph "attainable" if it is possible for cow ii to be at yy-coordinate YY at time T.T.

Subtask 1: O(N3)O(N3) BFS

Subtask 2: It can be shown that the shortest path between any two worlds contains at most one intermediate world. So for each query, iterate over all worlds aside from the start and the end and check if it can be the intermediate one in O(N2)O(N2) time. Alternatively, speed up the solution from subtask 1 with bitset.

Subtask 3: WLOG suppose that A[Qi]<Ai.A[Qi]<Ai. Clearly no attainable points lie below the lower convex hull of all lines representing worlds jj such that AjAiAj≥Ai. Furthermore, all points on this hull are attainable. Thus, it suffices to find the tt-coordinate of the intersection of the line y=Qit+A[Qi]y=−Qit+A[Qi] with this lower hull. We can compute the hulls for all ii by sorting the lines by AiAi in decreasing order and adding them to the hull one by one. This can be done using a deque. After computing the hull for i,i, we can binary search to find the intersection of the line with the hull.

Spencer's Code:

 

import java.io.*;
import java.util.*;

public class falling {
	public static class Obj implements Comparable<Obj>{
		public long y, d;
		public int ind;
		public Obj(long a, long b, int c) {
			y = a;
			d = b;
			ind = c;
		}
		public int compareTo(Obj o) {
			return Long.compare(y, o.y);
		}
	}
	public static long gc(long a, long b) {
		if(a==0L || b==0L) {
			return a+b;
		}
		return gc(b%a,a);
	}
	public static class Pair{
		public long first, second;
		Pair(long a, long b){
			first = a;
			second = b;
		}
	}
	public static Pair make_pair(long a, long b) {
		return new Pair(a,b);
	}
	public static Pair ev(Obj a, Obj b) {
		return make_pair(Math.abs(a.y-b.y),Math.abs(a.d-b.d));
	}
	public static int cmp(Obj a, Obj b, Obj c) {
		Pair l = ev(a,c);
		Pair r = ev(b,c);
		long res = l.first*r.second-r.first*l.second;
		if(res<0L) {
			return -1;
		}
		if(res==0L) {
			return 0;
		}
		return 1;
	}
	public static boolean used(Obj a, Obj b, Obj c) {
		Pair l = ev(a,b);
		Pair r = ev(b,c);
		long res = l.first*r.second-r.first*l.second;
		return (res<0L);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new FileReader("falling.in"));
		int n = Integer.parseInt(in.readLine());
		String[] line = in.readLine().split(" ");
		long[] a = new long[n];
		int[] q = new int[n];
		long[] num = new long[n];
		long[] dem = new long[n];
		for(int i = 0; i<line.length; i++) {
			a[i] = Integer.parseInt(line[i]);
		}
		line = in.readLine().split(" ");
		for(int i =0 ; i<line.length; i++) {
			q[i] = Integer.parseInt(line[i])-1;
		}
		ArrayList<Obj> li = new ArrayList<Obj>();
		ArrayList<Obj> all = new ArrayList<Obj>();
		for(int i = 0; i<n; i++) {
			li.add(new Obj(a[i],-(i+1),i));
			all.add(new Obj(a[i],-(i+1),i));
		}
		Collections.sort(li);
		ArrayList<Obj> cur = new ArrayList<Obj>();
		for(int i = li.size()-1; i>=0; i--) {
			Obj now = li.get(i);
			while(cur.size()>0) {
				if(now.d < cur.get(cur.size()-1).d) {
					cur.remove(cur.size()-1);
					continue;
				}
				if(cur.size()>1 && !used(now,cur.get(cur.size()-1),cur.get(cur.size()-2))) {
					cur.remove(cur.size()-1);
					continue;
				}
				break;
			}
			cur.add(now);
			int ind = li.get(i).ind;
			if(a[ind]>a[(int)q[(int)ind]]) {
				if(cur.get(0).d > -(q[ind]+1)) {
					num[ind]=-1;
				}
				else{
					int lo = 0;
					int hi = cur.size()-1;
 
					while(lo<hi){
						int mid = (lo+hi)/2;
						int l = mid;
						int r = mid+1;
						if(cur.get(r).d > - (q[ind]+1)){
							hi = l;
							continue;
						}
						int res = cmp(cur.get(l),cur.get(r),all.get((int)q[(int)ind]));
						if(res<0){
							hi = l;
						}
						else if(res==0){
							lo = l;
							hi = l;
						}
						else{
							lo = r;
						}
					}
					Pair got = ev(cur.get(lo),all.get((int)q[(int)ind]));
					long g = gc(got.first,got.second);
					num[ind] = got.first/g;
					dem[ind] = got.second/g;
				}
			}
		}
		cur.clear();
		for(int i = 0; i<li.size(); i++){
			Obj now = li.get(i);
			while(cur.size()>0){
				if(now.d > cur.get(cur.size()-1).d){
					cur.remove(cur.size()-1);
					continue;
				}
				if(cur.size()>1 && !used(now, cur.get(cur.size()-1), cur.get(cur.size()-2))){
					cur.remove(cur.size()-1);
					continue;
				}
				break;
			}
			cur.add(now);
			int ind = li.get(i).ind;
			if(a[ind]<a[(int)q[(int)ind]]){
				if(cur.get(0).d < -(q[ind]+1)){
					num[ind] = -1;
				}
				else{
					int lo = 0;
					int hi = cur.size()-1;
					while(lo<hi){
						int mid = (lo+hi)/2;
						int l = mid;
						int r = mid+1;
						if(cur.get(r).d < - (q[ind]+1)){
							hi = l;
							continue;
						}
						int res = cmp(cur.get(l),cur.get(r),all.get((int)q[(int)ind]));
						if(res<0){
							hi = l;
						}
						else if(res==0){
							lo = l;
							hi = l;
						}
						else{
							lo = r;
						}
					}
					Pair got = ev(cur.get(lo),all.get((int)q[(int)ind]));
					long g = gc(got.first,got.second);
					num[ind] = got.first/g;
					dem[ind] = got.second/g;
				}
			}
		}
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("falling.out")));
		for(int i = 0; i<n; i++){
			if (num[i]==-1) out.println(-1);
			else out.println(num[i]+"/"+dem[i]);
		}
		out.close();
	}
}

[/hide]

翰林国际教育资讯二维码