colorful grid

general
1 

lim=int(1000000007)
t = int(input())
for i in range(t):        
    n,c =input().split()
    n=int(n)
    c=int(c)
    if n%2==1:
        g1 =c**(5*n*n)%lim
        g2=(c**(n*n+(n*n+1)/2)) %lim
        g2 =2*g2
        g3 =c**(2*n*n+(n*n+1)/2) %lim
        print (int(((g1+g2+g3)/4))%lim)
    else :
        g1 =c**(5*n*n)%lim
        g2=(c**(n*n+(n*n)/4)) %lim
        g2 =2*g2%lim
        g3 =c**(2*n*n+(n*n)/2) %lim
        print (int(((g1+g2+g3)/4))%lim)

Link to the problem ICPC16E Problem - CodeChef

I have solved this problem but I am not able to pass the timelimit
Can someone tell the improvement in the code …

2

Just try to run with the following input:

3
1 1
1 2
100 3

You will get an overflow. In your code, you are calculating c to power O(n^2). Which is super exponential w.r.t. n. Just n=100 and c=2 leads to an overflow. Just think what will happen with the largest possible inputs. For example,

c = 10^9
n = 10^18

which will lead to c^10^36. That’s a HUGEEEE number. Obviously your code will break. Try to come up with another algorithm and think about when you should be using the MOD limit of 10^9+7.

There is a catch while writing Python codes. As the popular saying goes: With great power comes great responsibilities. Similarly, with great Python one liners, comes a great responsibility of understanding what’s going on behind the scene and what complexity a library call involves.

4 Likes
3

Your approach is wrong.