Блог пользователя pinkcorn

Автор pinkcorn, 10 лет назад, По-английски

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
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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!

»
10 лет назад, # |
  Проголосовать: нравится +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.

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

You can test it yourself using "Custom Invocation"

»
10 лет назад, # |
Rev. 7   Проголосовать: нравится +26 Проголосовать: не нравится
#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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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!

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

if am amnot wrong it is 2*10^8

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I use 10^8 as a rule of thumb

»
4 года назад, # |
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.

»
4 года назад, # |
  Проголосовать: нравится +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
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
  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
»
4 года назад, # |
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.