CCC '96 S5 - Maximum Distance

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 256M
Problem type

Consider two descending sequences of integers X[0 \ldots n-1] and Y[0 \ldots n-1] with X[i] \ge X[i+1] and Y[i] \ge Y[i+1] and for all i, 0 \le i < n-1. The distance between two elements X[i] and 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}

The distance between sequence X and sequence Y is defined by

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

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

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

           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 sequence and the second is the 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

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

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.

    1. On the next line: Another integer l.
    2. 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.