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

general
, ,
1

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;
}
2

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.

3 Likes
3 

import math

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

4

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

5

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