Speeding up Codechef FROGV
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 &lt; frogv.txt &gt; /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.)