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)

I removed every line of code, except for the input().split(). And it returns runtime error on the 10,000 element test case....

N <= 100,000 now. You'll need a better algorithm for 30 pts...
(The value will revert to 10 after the CCC.)

IF you're going to update the test cases (incrase the bounds), I would think the majority of us would want all of our previous submissions deleted because we lost points from this problem due to the update test cases (everyone is now at 3/10).

It wasn't really worth 10 points in the first place, though. I don't know why it was so high before

Then update the problem type too. 

when submitting java code the class name is that of the problem code...I believe that the second test case is looking for another name for the class. Yes? or is a problem in my algorithm?

Time limit exceeded.

for every element in the sequence, what is the limit. I was wondering if integer would work...

just do longint
P.S. finished this problem before u

But on Tp it wonk work with 100000.

PS.curses

there is a pascal compiler on the judge that allows u to declare an array of 100000 longints without exceeding the memory limit

This problem is very similar to the first problem that was on my CS 145 final exam at Waterloo. I'm sure almost everyone got 10/10 on it, though.

This isn't true, it's just a coincidence this works on the test data :P
As the problem statement says, the first number can be greater than or equal to - not just equal to.

Oh My God!! I DID IT!! it took me a while to learn scanf and printf though.. :(

you don't need to use scanf and printf to solve this problem

Yup, it only save about 0.26 seconds on my code so it shouldn't make a huge difference with your's either.

I wanted to though.. :)

Can you teach me scanf and printf?

We will teach it in class sometime. I have no idea why you're requesting to be taught it in this thread of comments about Max Distance...

If you really wanna learn, ask me, Hanson, or Brian personally or just look it up on the net.

I think he was joking.

Is it mass input then mass output or input then output right after?

Doesn't matter.
The judge basically puts all your output into a file, so input doesn't interfere (unlike on a screen).

I have 3/10, which is correct, but instead of getting 3/10 which is 9/30, I just have 3/10, which is 6 points less, which is important for me, so please correct this if you have the time.

The 30 point 'bonus' is a special offer, and doesn't apply to older submissions.
Solve it fully if you want more points.

thats not what I meant. My old submission accepted and was worth 10 points, which is worth 9/30 (3/10) now, because it is the old solution, but I only get three points for 9/30

Wow what do you not get.

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

6 points would be nice, and now it is 30% right on a 30 point problem.

why dont we just include a max distace 2 and make it worth 20 points so that 10+20=30

I think because Hanson thought that this problem with the easy test cases didn't deserve 10 points. 

can you delete my submission, still? It's ruining my chance to tie somebody./..

that wouldn't be fair, would it?