CCC '96 S5 - Maximum Distance - Olympiads Online Judge

CCC '96 S5 - Maximum Distance

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Consider two descending sequences of integers $X[0 \ldots n-1]$ $X [0 \dots n - 1]$ and $Y[0 \ldots n-1]$ $Y [0 \dots n - 1]$ with $X[i] \ge X[i+1]$ $X [i] \geq X [i + 1]$ and $Y[i] \ge Y[i+1]$ $Y [i] \geq Y [i + 1]$ and for all $i$ $i$ , $0 \le i < n-1$ $0 \leq i < n - 1$ . The distance between two elements $X[i]$ $X [i]$ and $Y[j]$ $Y [j]$ is given by

$\displaystyle d(X[i], Y[j]) = \begin{cases}j-i & \text{if }j \ge i \text{ and } Y[j] \ge X[i] \\ 0 & \text{otherwise}\end{cases}$ $d (X [i], Y [j]) = {\begin{cases} j - i & if j \geq i and Y [j] \geq X [i] \\ 0 & otherwise \end{cases}$

The distance between sequence $X$ $X$ and sequence $Y$ $Y$ is defined by

$\displaystyle d(X, Y) = \max \{d(X[i], Y[j]) \mid 0 \le i < n, 0 \le j < n\}$ $d (X, Y) = max {d (X [i], Y [j]) ∣ 0 \leq i < n, 0 \leq j < n}$

You may assume $0 < n \le 100\,000$ $0 < n \leq 100 000$ .

For example, for the sequences $X$ $X$ and $Y$ $Y$ below, their maximum distance is reached for $i = 2$ $i = 2$ and $j = 7$ $j = 7$ , so $d(X, Y) = d(X[2], Y[7]) = 5$ $d (X, Y) = d (X [2], Y [7]) = 5$ .

Copy

           i=2
            |
            v
X     8  8  4  4  4  3  3  3  1
Y     9  9  8  8  6  5  5  4  3
                           ^
                           |
                          j=7

Input Specification

The first sequence is the $X$ $X$ sequence and the second is the $Y$ $Y$ sequence. You may assume that the sequences are descending and of equal length. A pair of sequences is preceded by a number on a single line indicating the number of elements in the sequences. Numbers in a sequence are separated by a space, and each sequence is on a single line by itself. As usual, the first number in the input gives the number of test cases.

Sample Input

Copy

2
9
8 8 4 4 4 3 3 3 1
9 9 8 8 6 5 5 4 3
7
6 5 4 4 4 4 4
3 3 3 3 3 3 3

Sample Output

Copy

The maximum distance is 5
The maximum distance is 0

Comments

0

jerrycui07 commented on Nov. 1, 2024, 9:35 p.m.

Don't assume that all the numbers will be single digits, I did that for some reason

0

WEAVER commented on Sept. 16, 2024, 8:53 p.m.

WAYYY TOO HARDDD!!!!

0

Kirito commented on Dec. 24, 2022, 7:47 p.m.

The additional test case from WCIPEG has been added, worth 90% of points and all submissions have been rejudged.

44
Arihan10 commented on Feb. 17, 2019, 6:31 p.m. ← edited →
For anyone who doesn't understand this problem, you have to basically find the maximum distance between two values in the arrays given n times.

On line 1, there is a single integer n.

On the next line: Another integer l.

The next 2 lines contain two separate arrays of l integers.

Repeat steps 1 & 2 n times.

Hope this helps you understand the problem a bit better.