## CCC '96 S5 - Maximum Distance

View as PDF

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

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 Nov. 29, 2021, 5:53 p.m. edit 3

Just for anyone struggling with this problem, Y[j] >= X[i] otherwise the distance is 0, so if Y[j] = X[i] but i > j then the value is 0. Basically just do j - i for distance and not |j - i|.

• commented on Feb. 17, 2019, 1: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.

• commented on Dec. 28, 2017, 9:17 p.m.

why is this brute force question worthing 10 points?

• commented on Dec. 30, 2017, 2:24 a.m.

I think it was that teachers actually marked the CCC before, so they had to manually input everything instead of having generated test cases. RIP teachers. They probably wanted to make it look scary.

• commented on Dec. 29, 2017, 9:43 p.m. edited

I binary searched by successive submissions and it seems like

[Computers were probably too slow in 1996 but...]

• commented on Jan. 7, 2018, 8:38 p.m.

Yeah... the test cases seem a bit weak. The same problem on PEG has but I don't think a brute force approach passes due to the addition of more cases.