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)
(The value will revert to 10 after the CCC.)
P.S. finished this problem before u
PS.curses
As the problem statement says, the first number can be greater than or equal to - not just equal to.
If you really wanna learn, ask me, Hanson, or Brian personally or just look it up on the net.
The judge basically puts all your output into a file, so input doesn't interfere (unlike on a screen).
Solve it fully if you want more points.
Your old submittion was only 30% right. At the time it was worth 10 points. 30% times 10 is 3 POINTS.
6 points is life and death to you...?
why dont we just include a max distace 2 and make it worth 20 points so that 10+20=30