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

5*(10^9) operations working in less than 2 seconds!?
Автор Pedrams, 10 лет назад, По-английски

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;

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

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

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)

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

    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.

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

      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)

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

    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.

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

      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 ??

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

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

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

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

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

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится

      % is also very expensive.

      Better way:

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

      Output: 3565158400

      → Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for poining that clock() is too slow.

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

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

      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)

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

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

        #pragma GCC optimize("O3 strict-aliasing")
        → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить