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

×

C(AC) vs Python(TLE) in October Cook-Off Challenge's "Chef and Weird Queries" problem

For the problem Chef and Weird Queries was something wrong with compiler? First I submitted in Python and I got TLE. I tried 4 times. In the last, I submitted the same logic in C language and got AC. Can anyone tell why it happened? Complexity of Algorithm doesn't change after that I got TLE so penalty.

This is my Python2 solution

import math for _ in xrange(input()): y=input() k=0 for i in range(1,701): p=y-i if p<0: break a=int(math.sqrt(p)) k+=a print k

Here is my C solution
#include "stdio.h" #include "math.h" int main() { long long int i,j,t,a,k,y; scanf("%lld", &t); for(i=1;i<=t;i++) { scanf("%lld", &y); k=0; for(j=1;j<=700;j++) { long long int p = y-i; if(p<0) break; a = (int)math.sqrt(p); k+=a; } printf("%lld", k); if(i!=t) printf("\n"); } return 0; }

This question is marked "community wiki".

asked 23 Oct '17, 13:44

vichitr's gravatar image

5★vichitr
2555
accept rate: 11%

edited 23 Oct '17, 13:49


Sometimes you dont have any choice but to shift to a faster programming language.

Let me narrate what happened in a codeforces round once.

The first problem of the contest was really easy, its like you run a loop from $[1,{10}^{7}]$, and from the read input, check for sometime trivial like "Is it divisible by k" and thats it.

C++ code executes well within 0.01 second.

Python code gets a TLE, takes over 2 seconds. It couldnt perform those ${10}^{7}$ iterations within time of 2 seconds.

Then, another big bunch of codes get TLE or runtime error in python because recursion is $more$ expensive in python than in C++. Similar holds true for JAVA as well, where recursion is expensive.

Theres nothing we can do about it honestly. Even after 10x time bonus, some faults are too intrinsic to provide any relief for (w/o being unfair).

Hence, its usually advised that you switch to C++ for harder problems which have strict time limit.

link

answered 23 Oct '17, 15:39

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 23 Oct '17, 19:36

import math

Does this line affect the runtime? Won't importing whole Math module will take a lot of time?

link

answered 27 Oct '17, 18:38

vichitr's gravatar image

5★vichitr
2555
accept rate: 11%

No. That won't take any time compared to the iteration.

(27 Oct '17, 20:40) dhruvsomani3★

If just importing libraries in some languages tarts causing TLE, then that language is as good as dead lol

(27 Oct '17, 21:16) vijju123 ♦♦5★
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:

×795
×3
×3

question asked: 23 Oct '17, 13:44

question was seen: 372 times

last updated: 27 Oct '17, 21:16