You are not logged in. Please login at www.codechef.com to post your questions!

×

colorful grid

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 https://www.codechef.com/problems/ICPC16E

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

asked 21 Jul '17, 16:34

mabrinmacro's gravatar image

3★mabrinmacro
11
accept rate: 0%

edited 21 Jul '17, 16:36


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.

link

answered 21 Jul '17, 17:04

utkalsinha's gravatar image

5★utkalsinha
723118
accept rate: 12%

edited 21 Jul '17, 17:09

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×4

question asked: 21 Jul '17, 16:34

question was seen: 197 times

last updated: 21 Jul '17, 17:09