pinkcorn's blog

By pinkcorn, 9 years ago, In English

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!

  • Vote: I like it
  • +11
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can test it yourself using "Custom Invocation"

»
9 years ago, # |
Rev. 7   Vote: I like it +26 Vote: I do not like it
#include<stdio.h>
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<stdio.h>
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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    The fact is that the module should be 4294967296 instead of 2147483648, because of unsigned int.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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!

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

if am amnot wrong it is 2*10^8

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I use 10^8 as a rule of thumb

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also used it as thumb rule and got stuck Solve this

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

»
4 years ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it
  1. First, it depends on language you use -> read this

  2. 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

  3. It depends on compiler optimization, some optimizations can actually boost your program significantly, like below C++ program

With -O2 flag
»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.