CCC '96 S5 - Maximum Distance - DMOJ: Modern Online Judge

CCC '96 S5 - Maximum Distance

Points: 10

Time limit: 2.0s

Memory limit: 16M

Problem type

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

$d(X[i], Y[j]) = j - i$ ~d(X[i], Y[j]) = j - i~ if $j \ge i$ ~j \ge i~ and $Y[j] \ge X[i]$ ~Y[j] \ge X[i]~, or $0$ ~0~ otherwise

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

$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$ ~0 < n \le 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~.

           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

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

12
Arihan10 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.

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

Arihan10 commented on Feb. 3, 2019, 12:31 a.m. ← edit 2 →

Can someone help me understand this a bit better?
6

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

why is this brute force question worthing 10 points?

3

Roynaruto 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.
3

jkguipqnjcy49979693 commented on Dec. 29, 2017, 9:43 p.m. ← edited →

I binary searched by successive submissions and it seems like $\displaystyle n \le 25$ $$\displaystyle n \le 25$$

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

1

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

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