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 ji 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)

<
1
2
>

As the problem type says :'(