Pedrams's blog

5*(10^9) operations working in less than 2 seconds!?
By Pedrams, 10 years ago, In English

Hi everyone.

I saw a code in the "Status" tab today, which made me wonder: <<How does it work in less than 2 seconds?>> Its number of operations was about (5 * 10^9)...

So my question is: How many operations can exactly be done in 1 second, here in Codeforces?

To be more clear, this is the problem: 287B - Трубопровод And this is the submission: 4075576

(1 ≤ n ≤ 10^18, 2 ≤ k ≤ 10^9) * see test #4 * the answer is (-1), so we are sure that k reaches 0

Recently, I wrote two codes for this problem. Code #1 gets "Time limit exceeded" while code #2 gets "Accepted". What's the differences which cause this problem?

// code #1
#include <bits/stdc++.h>
using namespace std;
	
typedef long long LL;
LL n, k;
LL sum, ans;

int main()
{
    ios::sync_with_stdio(false);
    freopen("B.in", "r", stdin);
    n = 1e18;
    k = 1e9;
    sum = 1;
    while(--k && sum < n)
    {
        sum += k;
        ans++;
    }
    if(sum < n)
        cout << -1 << endl;
    else
        cout << ans << endl;
		
    return 0;
}

// code #2 -- equal to the submission I said.
#include<stdio.h>
int main()
{
    __int64 n,res=1;
    int k,ans=0;
    scanf("%I64d %d",&n,&k);
    while(res<n&&k>=2)
    {
        --k;
        res+=k;
        ++ans;
    }
    printf("%d\n",res>=n? ans: -1);
    return 0;
}

** Even when I write this code at the end of both of them, surprisingly code #1 shows something about 3.5 seconds and code #2 shows something about 4 seconds!! cout << (double)clock()/CLOCKS_PER_SEC << endl;

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

Comments Comments (15)
| Write comment?
»
10 years ago, # |
  Vote: I like it -28 Vote: I do not like it

Actually, CF does around 7 * 10^7 operations per second. You can see this by submitting this code into the 'Run' tab:

#include <ctime>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int cnt = 0;
    while (clock() < 1000) ++cnt;
    cout << cnt << "\n";
}

But I think, compiler greatly optimized solution. -O2 is a smart thing though :o)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    OFT,I just know about -O2 optimization yesterday

    ‪#‎include‬ <iostream>
int main() {
for (int i = 0; i < 4; ++i)
std::cout << i*1000000000 << std::endl;
}


    This code will enter in Inf loop if you used -O2 optimization.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      However, this code doesn't:

      #include <iostream>
int main() {
  for (int i = 0; i < 4; ++i)
    std::cout << (int)((unsigned)i*1000000000) << std::endl;
  return 0;
}

      It's a very good example of what's called undefined behavior. Complier has the right to assume that signed overflow does not occur at any time. Based on that assumption, he optimizes the for loop, because if i>=4, then overflow happens and it's undefined behavior. If you want some variable to overflow, use unsigned types.

      Another examples of UD are shifts by negative number (like 1 << (-2)) or shifts of negative values (like -1 << 20)

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    clock() is very slow, you'd better not call it in the bottleneck. For example, the following code:

    #include <cstdio>

int main() {
  int n;
  scanf("%d", &n);
  long long sum = 0;
  while (n --> 0) sum += n;
  printf("%I64d\n", sum);
  return 0;
}

    takes 623 ms on Codeforces to run when n = 109.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      So does it mean: 3*(10^9) operations in about 600 ms ==> 10^9 operations in about 200 ms ==> 10^10 operations in about 2 seconds ??

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

        i don't think so. a lot of compiler optimizations happen while generating executable, without which i suspect that yeputons's code will take more than 5 seconds to run (for n = 109).

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it 
    #include <ctime>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int cnt = 0;
    while (cnt % 1000 || clock() < 1000) ++cnt;
    cout << cnt << "\n";
}

    Output: 435594000

    All I want to say is that clock() is very expensive, so you example is incorrect :)

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

      Oh, that's interesting, didn't know about that. Thanks :)

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +27 Vote: I do not like it

      % is also very expensive.

      Better way:

          unsigned int cnt = 0;
    const int T = (1<<20) - 1;
    while ((cnt & T) || clock() < 1000) ++cnt;

      Output: 3565158400

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for poining that clock() is too slow.

    Btw does anyone know, how to override compilation flags from the program?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      What for? I think it almost impossible, but MSVC++, for instance, allows you to specify stack size and what libraries does your program need (and, I think, another options to linker) via #pragma comment(linker)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        It's possible for GCC options that begin with -O or -f:

        #pragma GCC optimize("O3 strict-aliasing")
        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In this Example s/he only iterate 10^9 times with light operation ( + operator doesn't cost huge time )
calculate time complexity with tough test cases need from you not only calculate complexity but also test your code with large testcases on the codeforces itself.
2 SRMs ago I submit c++ code with complexity O(N*N*Log2(N)) and Max N is 4000 which contains maximum ~ 4*10^8 operation but get TLE and other solutions with the same complexity but different implementation Passed.
so
First you have to calculate complexity just to know your Algorithm will be feasible or not.
Second if it's feasible try to test it with tough testcases in the same position you will submit your code on it.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

excuse me maybe i'm wrong but i think the code will have at most x operations that : x * (x + 1) <= 2 * (1e18 + 1) which means x <= 1e9

→ Reply