Speeding up Codechef FROGV

Question

This is my solution to the FROGV problem on Codechef:

N,K,P = map(int,raw_input().split(' ')) # N: No of Inputs, K: highest possible jump, P: no of test cases
L = map(int,raw_input().split(' ')) # Takes in the N space separated inputs
Li = sorted(L)
Breaks = [] #Records the starting point a of pair a,b such that the jump from a to b is larger than k
for i in xrange(0,N-1):
 if Li[i+1]-Li[i] > K: # The difference basically gives the jump size 
 Breaks.append(Li[i])
for i in xrange(0,P): # Checking over each pair
 a,b = map(int,raw_input().split(' '))
 a,b = a-1,b-1 # The pairs use numbering from 1 to n while python numbering is from 0 to n-1
 for Break_Pt in Breaks:
 if (abs(L[a]-L[b])>K) and (((L[a]<=Break_Pt and Break_Pt<L[b]) or (L[b]<=Break_Pt and Break_Pt<L[a]))): # If the jump from a to be is greater than K then it checks whether there is a break pt in between a and b.
 print 'No'
 break
 else:
 print 'Yes'

Codechef tells me that this code exceeds the time limit, but I couldn't find any way to improve the speed.

• Gareth Rees: Have you measured the performance of your code? What test case did you use?
• user3813920: I checked it on their example, nothing else.

Answer 1

You said that only checked your code against the example on Codechef. But the example only has 5 frogs and 3 pairs! Running this tiny example won't tell you how your code will perform on the worst case, where there might be 100,000 frogs and 100,000 pairs.

So the first step is to make a test for the worst case. This is easily done, for example with a function like this:

from __future__ import print_function
import random
def frogv_test(N=10**5, P=10**5, file=None):
 """Make a test case with N frogs and P pairs; write it to file."""
 M = 10**9 # Maximum coordinate of frog
 K = 4 * M / N # Make sure there are lots of "breaks"
 print(N, K, P, file=file)
 print(*(random.randrange(M) for _ in range(N)), file=file)
 for _ in range(P):
 print(*(1 + random.randrange(N) for _ in range(2)), file=file)

Let's see how your program performs on this test case:

$ time python2.7 cr56451.py < frogv.txt > /dev/null
real 0m48.012s
user 0m40.880s
sys 0m0.400s

48 seconds! That's bad, given that the time limit at Codechef is 1 second (and of course one would like to have a decent margin in case Codechef is running on slower hardware).

So, how can you speed it up? Well, the most important thing to look at is the time complexity of the algorithm. If you look at the structure of your code, you can see that you iterate over the pairs, and then for each pair, you iterate over the breaks:

for i in xrange(0,P):
 # ...
 for Break_Pt in Breaks:
 # ...

There are \$P\$ pairs, and there are \$O(N)\$ breaks: there might be a break between every two adjacent frogs. So the inner loop might have to be executed \$O(NP)\$ times! I put a counter in the inner loop, and sure enough, in this test case the inner loop was executed 60,897,434 times.

(That should be plenty for you to go on: I won't spoil the challenge for you by giving away the solution.)