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!
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
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!
Name |
---|
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.
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!
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.
You can test it yourself using "Custom Invocation"
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)
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.
The fact is that the module should be 4294967296 instead of 2147483648, because of unsigned int.
Thanks, fixed it~!
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!
if am amnot wrong it is 2*10^8
I use 10^8 as a rule of thumb
I also used it as thumb rule and got stuck Solve this
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.
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.
Codeforces runs way more than 1e9. Check in the custom test.
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$$$: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
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.