### 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-iifj≥iand 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)

qinhaotianon Dec 22, 2008 - 10:58:32 pm UTC No more simple for loop