1996 Canadian Computing Competition, Stage 1
Problem E: Maximum Distance
Consider two descending sequences of integers X[0..n-1]
and Y[0..n-1] with
X[i] ≥ X[i+1] and
Y[i] ≥ Y[i+1] and for all i,
0 ≤ i < n - 1.
The distance between two elements X[i] and Y[j]
is given by
d(X[i], Y[j]) = j - i if j ≥ i and Y[j] ≥ X[i], or 0 otherwise
The distance between sequence X and sequence Y is defined by
d(X, Y) = max{d(X[i], Y[j]) | 0 ≤ i < n, 0 ≤ j < n}
You may assume 0 < n ≤ 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
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
All Submissions
Best Solutions
Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 28, 2008
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)