UVA online p957 - "Popes"
When you tackle a programming challenge like this, it's a good idea to test out your program to see if it's fast enough, before you submit it. The problem description usually tells you how big the worst case is going to be, so it's a good idea to make a test case that's as big as the worst case, and then try out your program on it.

In this case, the problem description says,


  Each of the remaining \$P\$ lines contains the year of election of a Pope, in chronological order. We know that \$P≤100000\$ and also that the last year \$L\$ in the file is such that \$L≤1000000\$, and that \$Y ≤L\$.


So there could be as many as 100,000 popes! Let's make some sample data using this program:

Y = 100                         # Years in range of interest.
P = 100000                      # Number of popes
L = 1000000                     # Maximum year.
print(Y)
print(P)
for i in range(P):
    print(i * L // P)


Let's try it:

$ python make-popes-data.py &gt; popes.txt
$ /usr/bin/time python cr150204.py &lt; popes.txt
10 0 90
        0.71 real         0.65 user         0.05 sys


That doesn't seem so bad — 0.71 seconds. But remember that the problem statement says that \$Y\$ might be large — perhaps as large as \$L\$. So let's increase \$Y\$ to 1,000 and try again:

$ /usr/bin/time python cr150204.py &lt; popes.txt
100 0 990
        4.25 real         4.19 user         0.05 sys


That would already fail the 3 second time limit at UVa Online Judge. But what if \$Y\$ was even larger? Let's increase \$Y\$ to 10,000 and try again:

$ /usr/bin/time python cr150204.py &lt; popes.txt
1000 0 9990
       45.04 real        44.70 user         0.17 sys


45 seconds! So it should be clear now what the problem is. The code in the post has two nested loops. The outer loop is over all the popes:

for i in range (N_P):


and the inner loop is over the popes that are elected less than \$Y\$ years after pope number \$i\$:

while(popes[j] &lt;= popes[i] + Y):


So if \$Y\$ is big, then the inner loop might have to loop over a large fraction of the popes — and to do so for every pope in the outer loop. This is quadratic runtime behaviour.

You need to change the program so that it doesn't have this behaviour. But how can you do that? For this problem, the thing to do is to think about how you would solve the problem by hand. You might start with the first pope and count the popes that are elected in the next \$Y\$ years. But at that point you wouldn't throw away all your work and start again with the second pope — instead you would ... well, I don't want to spoil it for you!