USACO

USACO 2020 January Contest, Platinum

Problem 3. Falling Portals

Contest has ended.

Log in to allow submissions in analysis mode

There are

$N$ (

$2\le N\le 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\le A_i\le 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\le 100.$
Test cases 4-5 satisfy $N\le 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,\ldots,A_N.$

The next line contains $N$ space-separated integers $Q_1,Q_2,\ldots,Q_N.$

OUTPUT FORMAT (file falling.out):

$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

Contest has ended. No further submissions allowed.