1
\$\begingroup\$

This is my code:

n = int(raw_input())
seq = raw_input().split()
def minimize_list(lst):
    new_lst = []
    k = len(lst)
    for i in range(k-1):
        new_lst.append(lst[i+1]-lst[i])
    return new_lst
for i in range(len(seq)):
    seq[i] = int(seq[i])
final_list = []
for num in seq:
    final_list.append(num)
while len(final_list) != 1:
    final_list = minimize_list(final_list)
print (final_list[0])%(1000000000+7)

It takes a number and a sequence of numbers. (The first number is the number of numbers in the sequence). It then calculates a shorter sequence with the difference of adjacent numbers until there is just 1 number. Unfortunately, The time complexity is not good enough. I have to make it better to meet the time limit which is 1 second.

Any idea?

Note: I cannot see the input. I can just pass my code to a server which has 10 examples and runs my code on them. The server then tells me that this code has exceeded the time limit for some examples.

Update: I want to print (final_list[0])%(1000000000+7)

\$\endgroup\$
  • \$\begingroup\$ Do you have any example input and output? This usually makes these problems way easier to understand. \$\endgroup\$ – Graipher Jul 6 '18 at 14:28
  • \$\begingroup\$ @Graipher I do not know anything about the input. \$\endgroup\$ – newbie mathematician Jul 6 '18 at 14:29
  • \$\begingroup\$ Do you at least have a link to the problem statement? \$\endgroup\$ – Graipher Jul 6 '18 at 14:30
  • \$\begingroup\$ @Graipher I do! But it's in Persian (not English) \$\endgroup\$ – newbie mathematician Jul 6 '18 at 14:38
2
\$\begingroup\$

One easy way is to use numpy, which is implemented in C (if it is available on the machine your online judge is running on). It provides fast ways to do numerical calculations. In this case, you can use numpy.diff, which calculates the difference between elements. It even has a n argument, so it applies it n times. We also know how often we need to apply it to get only a single element, len(seq) - 1 times:

import numpy as np

n = int(raw_input())
seq = map(int, raw_input().split())
print np.diff(seq, len(seq) -1)[0]

If you need to stick to built-in methods, you could at least make the minimize_list method a bit shorter using a list comprehension (and maybe rename it to diff):

def diff(x):
    return [b - a for a, b in zip(x, x[1:])]

def reduce_diff(seq):
    while len(seq) > 1:
        seq = diff(seq)
    return seq[0]

if __name__ == "__main__":
    n = int(raw_input())
    seq = map(int, raw_input().split())
    print reduce_diff(seq)

I also removed the redundant copying from seq to final_list and instead of the for loop to convert all values to integers I used map.

Be aware that if you want to use this with Python 3 (as you should, since Python 2 will be obsolete soon), you need to surround that map call with a call to list and replace raw_input with input.

In addition I added a if __name__ == "__main__": guard to allow importing from this script from another script.


And finally, one can notice that this approach is \$\mathcal{O}(n^2)\$. When looking at a simple example of successive application of diff, a pattern becomes obvious:

\$ a, b, c, d, e\\ b-a, c-b, d-c, e-d\\ c-2b+a,d-2c+b, e-2d+c\\ d-3c+3b-a, e-3d+3c-b\\ e-4d+6c-4b+a \$

The coefficients are the ones from Pascals triangle, together with an alternating sign:

\$ \begin{pmatrix} & & & & 1 & & & &\\ & & & 1 & & 1 & & & \\ & & 1 & & 2 & & 1 & & \\ & 1 & & 3 & & 3 & & 1 & \\ 1 & & 4 & & 6 & & 4 & & 1 \end{pmatrix} \$

So, if you find a fast way to calculate the n-th row of Pascal's triangle, you can solve this problem in \$\mathcal{O}(n)\$, by adding the terms with a plus, modulo p and the ones with a minus, modulo p and then subtract them:

from itertools import cycle

def pascal_line(n):
    line = [1]
    mid, even = divmod(n, 2)
    line_append = line.append
    for k in xrange(1, mid + 1):
        num = line[k-1]*(n + 1 - k)//(k)
        line_append(num)
    reverse_it = reversed(line)
    if not even:
        next(reverse_it)
    line.extend(reverse_it)
    return line

def reduce_pascal(seq):
    return sum(sign * c * x
               for sign, c, x in zip(cycle([1, -1]),
                                     pascal_line(len(seq)-1),
                                     reversed(seq)))

if __name__ == "__main__":
    n = int(raw_input())
    seq = map(int, raw_input().split())
    p = 1000000000+7
    print reduce_pascal(seq) % p

One could make this also modular p at each step by doing the sum manually and enforcing the mod p.

Beware: This seems to break down for large sequences (since the terms in the triangle get big).

\$\endgroup\$
  • \$\begingroup\$ Isn't there any built-in module instead of numpy? The server does not support it. \$\endgroup\$ – newbie mathematician Jul 6 '18 at 14:40
  • \$\begingroup\$ @ArmanMalekzadeh Added some built-in code. \$\endgroup\$ – Graipher Jul 6 '18 at 14:47
  • \$\begingroup\$ Actually, I want to print (seq[0])%(1000000000+7) . Is there a fast way to calculate that value with built-in functions? (I know i didn't mention that in my question. But just in case you know...) \$\endgroup\$ – newbie mathematician Jul 6 '18 at 14:51
  • \$\begingroup\$ I uploaded the code to the server and it's still not good enough. \$\endgroup\$ – newbie mathematician Jul 6 '18 at 15:10
  • 2
    \$\begingroup\$ It may help that you can calculate the binomial coefficients modulo a prime number p with Lucas's theorem, that will limit the size of intermediate results. For the special case p=3 that was done here. \$\endgroup\$ – Martin R Jul 6 '18 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.