Central Delannoy numbers

I am solving this problem on SPOJ Upper Right King (Hard):


There is a king in the lower left corner of the \$ n \times n \$ chess board. The king can move one step right, one step up or one step up-right. How many ways are there for him to reach the upper right corner of the board? Give the answer modulo 1000003.

The numbers to be output are the central Delannoy numbers.

I've written a solution in Python with a time complexity of \$ O(n(\log m)^2) \$. But it's showing "time limit exceeded". Can anyone help me out with this?

import math
MAX = 10000002
MOD = 1000003

# Extended euclidean algorithm for modular inverse

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return 0
    else:
        return x % m

t = raw_input()
t = long(t)

fact = []

for i in range(0,MAX):
    fact.append(0)
fact[0]=1
fact[1]=1
for i in range(2,MAX):
    fact[i] = (i%MOD * fact[i-1]%MOD)%MOD

while t:
    n = raw_input()
    n = long(n)
    n = n-1
    Sum = 1
    prod = ((n+1)%MOD * (n)%MOD)%MOD
    increment = n+1
    decrement = n
    Sum = (Sum%MOD + prod%MOD)%MOD

    for k in range(0,n-1):
        temp_prod = (prod%MOD * (increment+1)%MOD * (decrement-1)%MOD)%MOD
        prod = temp_prod
        fct = fact[k+2]
        fat2 = (fct%MOD * fct%MOD)%MOD
     #   print fat2,modinv(fat2,MOD)
        result = (temp_prod%MOD * modinv(fat2,MOD))%MOD
        Sum = (Sum%MOD + result%MOD)%MOD
        increment = increment + 1
        decrement = decrement - 1

    print "%ld" %(Sum)
    t = t-1

How can I reduce the complexity of this problem in order to have it accepted?

Flatten your method body

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

can be re-written as:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

because returning halts the function.

Use in-line 'ternary' to reduce verbosity

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return 0
    else:
        return x % m

should become

def modinv(a, m):
    g, x, y = egcd(a, m)
    return 0 if g != 1 else x % m

Say something meaningful when asking for input

t = raw_input()

The user sees nothing, only an hanging interpreter.

Use a main function

• Python code runs faster in functions

• You can use an if name ... block to avoid execution when the module is imported.

Convert directly (minor)

Do not waste lines:

n = raw_input()
n = long(n)

should become

n = long(raw_input()) # <- also add a meaningful prompt

Follow naming conventions (minor)

You follow the naming conventions pretty well, just one imprecision:

Sum = 1

should be:

sum = 1

Use proper spacing (minor)

For example this line:

prod = ((n+1)%MOD * (n)%MOD)%MOD

is hard to read because all the symbols are squashed together.

Modularize more (important)

You defined two functions, that is very good, but you could do more to reduce the 35 lines of top level imperative code that is too much.

Usually each function (including main) should be no more than 10-15 lines of code.

Use doctests to for automatic testing

In Math code, automatically testing your functions each time you run the programme can be invaluable, just use something like:

import doctest

def egcd(a, b):
    """
    Meaningful description here...

    >>> egcd(4132, 434)
    (2, -48, 457)
    """

    if a == 0:
        return (b, 0, 1)

    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)

doctest.testmod()

and the code will be tested automatically.

Tell why

I can see many calculations in your code, but why? Following which algorithm, please write this inside the docstrings of your functions.

StackExchange Code Review Q#33575, answer score: 2