### pinkcorn's blog

By pinkcorn, 6 years ago,

I know the topcoder judging system and that it will allow a 10^9 solution to pass provided every operation is trivial. Will a 10^9 solution pass in codeforces? If not what can be the Big-O complexity of my solution so that it passes? Thanks!

• +11

 » 6 years ago, # |   +9 It depends on what type of operation you perform. If it is a simple for loop or something, it would be done in 2 seconds. But if you call a recursion function 10^9 times, even if it is a simple factorial function, it cannot be done in 2 seconds, I think.
•  » » 6 years ago, # ^ |   0 Yup, with recursion there is the overhead of setting up a new stack for every function call, so a 10^9 solution is likely to fail. My question was mainly intended towards non-recursive solutions. Thanks for the answer!
 » 6 years ago, # |   +3 If you do exactly 10^9 operations it may pass, but even a little more could not fit in 2 seconds. And also it depends on the language you are writing in. So if you are solving a problem here with any bound <= 10^9 you should not be able to get a solution that makes 10^9 operations, because as I said the chance to do <= 10^9 operations with that bound is very small. I cases like that you cant iterate and it is better start writing a log(N) solution, because it is bad to waste time.
 » 6 years ago, # |   +3 You can test it yourself using "Custom Invocation"
 » 6 years ago, # | ← Rev. 7 →   +26 #include int main() { int sum=0; for(int i=1;i<=1000000000;++i) sum=(sum+i)%1000000007; printf("%d\n",sum); } This is a code to calculate one billion plus and mod operators between two integers. It spends 3260 ms to solve the correct answer 21 for (1+2+...+1000000000)%1000000007 If you don't output the value of sum, the compiler seems to ignore the calculation of sum as well as the loop, and spends 0 ms. If you delete the mod operator, and change int into unsigned int (that means mod 4294967296) #include int main() { unsigned int sum=0; for(int i=1;i<=1000000000;++i) sum=sum+i; printf("%u\n",sum); } It costs only 514 ms. That seems that mod(%) will cost 5 times more than plus(+). So it is so hard to say how many operators, because some operators like plus cost little time and some like mod cost much time.
•  » » 6 years ago, # ^ |   +18 The fact is that the module should be 4294967296 instead of 2147483648, because of unsigned int.
•  » » » 6 years ago, # ^ |   0 Thanks, fixed it~!
•  » » 6 years ago, # ^ |   0 Its quite surprising that the compiler actually optimizes to not calculating sum when printf is not given(How can the compiler decide that I don't use the variable sum when I'm clearly doing sum=sum+1?). But I get the idea about what will and won't pass. Thanks!
 » 14 months ago, # |   +1 if am amnot wrong it is 2*10^8
 » 14 months ago, # |   +5 I use 10^8 as a rule of thumb
•  » » 10 months ago, # ^ |   0 I also used it as thumb rule and got stuck Solve this
•  » » » 6 weeks ago, # ^ |   +3 it's a rule of thumb, it's implied that it's not exact and won't always work but it is intended to be a good approximation.
•  » » 2 months ago, # ^ | ← Rev. 2 →   -22 Oh okay
 » 8 months ago, # | ← Rev. 2 →   -11 for c++ consider 10^9 operations per second, this will also work for slowest operations, so you don't have to worry about mod or plus or recursive operations and there is always a way to solve a question in less than 2*10^7 (Usually time limit is 2000 ms) operations.
•  » » 8 months ago, # ^ |   0 Codeforces runs way more than 1e9. Check in the custom test.
 » 2 months ago, # |   +3 Depends on what kind of operation you're doing.If you're jumping over values in a permutation (repeating x = p[x]), you could do that only a few million times per second. If you're finding the maximum value in an array with proper optimizations, you can do that for total array sizes of up to 10 billion ints. You can try the code below on custom invocation with $n=k=100000$: Code#pragma GCC optimize("O3") #pragma GCC target("avx2,tune=native") #include using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(!cin.tie(0)); mt19937 eng(8888); int n, k; ll z = 0; cin >> n >> k; vector a(n); for (int& x : a) x = eng(); while (k--) { z += *max_element(begin(a), end(a)); } cout << z << '\n'; } 
 » 2 months ago, # |   +3 First, it depends on language you use -> read this It depends on operations you doing, if you do such bitwise operations (shift left, shift right, and, or, xor, not) it seems very fast, while some arithmetic operations (multiple, divide, modulo) it costly and run slower It depends on compiler optimization, some optimizations can actually boost your program significantly, like below C++ program With -O2 flag#pragma GCC optimize("O2") #include using namespace std; int main() { long long cnt = 0; for (long long i = 0; i < 1e18; ++i) ++cnt; cout << cnt; return 0; } 
 » 2 months ago, # | ← Rev. 3 →   0 The general rule of thumb I'm aware of is $5 \cdot 10^8$ operations in total for C++. Sometimes the runtime may be higher or lower and permit more or less operations.