CCC '96 S5 - Maximum Distance

View as PDF

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem type

Consider two descending sequences of integers and with and and for all , . The distance between two elements and is given by

The distance between sequence and sequence is defined by

You may assume .

For example, for the sequences and below, their maximum distance is reached for and , so .

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

• 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.

• 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.