How many Number of operations are accepted on Codechef under 1 sec ?

Also what would be the greatest upper-bound function of time complexity that would run in under 1 sec ?

I always try to suit my solution in the range of about 10^6-10^7 operations and it never exceeds time limit . And the upper bound function depends upon the problem you are doing . Every problem has its own upper bound.

Somewhere between 1e8 and 1e9

Its simple.

When your code is taking 1e9 operations, then you cannot apply usual theory. You have to consider constant, and other factors. In best circumstances, a code having cheap operations, can do 1e9 in 1 second. Now just add something costly like pow function in it, and it will take over 5seconds.

Have a strict upper limit and {10}^{8}. If you are in range pf {10}^{7}, hardware optimizations wont matter, but in range of {10}^{8}, even a constant factor K=20 can time out your code. Its really sensitive in this region, so give your best every time you can.

1 Like

Sometimes when my program runs in 1e9 operations on a problem with time limit 1 sec it gives me TLE.

That’s because operations are 1e9 but you didn’t consider the ‘extra’ work the cpu might have to do depending on the operations you’ve used. For example you cannot multiply long integers 1e9 times since multiplication is costly. ( You can add/subtract them since addition and subtraction is comparatively cheaper)

1 Like

I just tried running this code

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
    ll cnt=0;
    ll x;
    cin>>x;
    for(ll i=1;i<=x;i++)
    cnt=(cnt+1);
    cout<<cnt;
	return 0;
}

with input of 10^18 and it ran in 0sec time,
but changing cnt=(cnt+1); to cnt=(cnt+1)%10;
produced TLE even after changing the input to 10^10,

with input of 10^9 it ran in 4.2 sec time…

Is the ++ operation so light that it doesn’t affect the Time Complexity?

modulus is costly operation , %10 is the reason for you tle . Btw ++ is lighter than doing cnt=cnt+1

Compiler is a little more smart than you give it credit for dear. Mostly it is the case of compiler removing the loop (and replacing it with an equivalent assignment statement or so - not very sure about the replacement)

3 Likes