UVA online p957 - "Popes"

Question

This is the "Popes" problem from UVa Online Judge:

On the occasion of Pope John Paul II's death, the American weekly magazine Time observed that the largest number of Popes to be selected in a 100-year period was 28, from 867 (Adrian II) to 965 (John XIII). This is a very interesting piece of trivia, but it would be much better to have a program to compute that number for a period of any length, not necessarily 100 years. Furthermore, the Catholic Church being an eternal institution, as far as we can predict it, we want to make sure that our program will remain valid per omnia secula seculorum.

Write a program that given the list of years in which each Pope was elected and a positive number \$Y\$, computes the largest number of Popes that were in office in a \$Y\$-year period, and the year of election for the first and last Popes in that period. Note that, given a year \$N\$, the \$Y\$-year period that starts in year \$N\$ is the time interval from the first day of year \$N\$ to the last day of year \$N+Y−1\$. In case of a tie, that is, if there is more than one \$Y\$-year period with the same largest number of Popes, your program should report only the most ancient one.

I am a Python beginner. When I submit this code, it says "time limit exceeded". How can I optimize this code?

while True:
    try:
        str=input()
        if len(str):
            Y = int( str )
        else:
            Y = int( input() )
    except:
        break   
    N_P = int( input() )
    popes= []
    for i in range (N_P):
        popes.append( int(input()) )
    Y = Y-1
    maximum = 0
    for i in range (N_P):
        j = i
        count = 0
        while(popes[j] <= popes[i] + Y):
            j = j+1
            count = count +1
            if j>= N_P:
                break
            if count>maximum:
                maximum = count
                first = popes[i]
                last = popes[j-1]
    print (maximum,first,last)

Answer 1

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 > popes.txt
$ /usr/bin/time python cr150204.py < 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 < 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 < 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] <= 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!