Home » 国际竞赛 » Details

USACO 2020 January Contest, Platinum Problem 3. Falling Portals

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月1日下午6:24

USACO 2020 January Contest, Platinum Problem 3. Falling Portals

There are $N$ ( $2 \leq N \leq 2 \cdot 10^{5}$ ) worlds, each with a portal. Initially, world $i$ (for $1 \leq i \leq N$ ) is at $x$ -coordinate $i$ , and $y$ -coordinate $A_{i}$ ( $1 \leq A_{i} \leq 10^{9}$ ). There is also a cow on each world. At time $0$ , all $y$ -coordinates are distinct and the worlds start falling: world $i$ moves continuously in the negative- $y$ direction at a speed of $i$ units per second.

At any time when two worlds are at the same $y$ -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 $i$ , the cow on world $i$ wants to travel to world $Q_{i}$ ( $Q_{i} \neq i$ ). Help each cow determine how long her journey will take, if she travels optimally.

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

SCORING:

Test cases 2-3 satisfy $N \leq 100.$
Test cases 4-5 satisfy $N \leq 2000.$
Test cases 6-14 satisfy no additional constraints.

INPUT FORMAT (file falling.in):

The first line of input contains a single integer $N .$ The next line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N} .$

The next line contains $N$ space-separated integers $Q_{1}, Q_{2}, \dots, Q_{N} .$

OUTPUT FORMAT (file falling.out):

Print $N$ lines, the $i$ -th of which contains the journey length for cow $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 $2$ worlds 1 and 2 align, so the cow can travel to world 1. At time $\frac{7}{2}$ 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 .$ Consider a graph of time versus $y$ -coordinate; then world $i$ is represented by a line of slope $- i$ . Call a point $(T, Y)$ on this graph "attainable" if it is possible for cow $i$ to be at $y$ -coordinate $Y$ at time $T .$

Subtask 1: $O (N^{3})$ 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 (N^{2})$ time. Alternatively, speed up the solution from subtask 1 with bitset.

Subtask 3: WLOG suppose that $A [Q_{i}] < A_{i} .$ Clearly no attainable points lie below the lower convex hull of all lines representing worlds $j$ such that $A_{j} \geq A_{i}$ . Furthermore, all points on this hull are attainable. Thus, it suffices to find the $t$ -coordinate of the intersection of the line $y = - Q_{i} t + A [Q_{i}]$ with this lower hull. We can compute the hulls for all $i$ by sorting the lines by $A_{i}$ 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,$ 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]