### Pedrams's blog

By Pedrams, 5 years ago, ,

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 - Pipeline 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
•

 » 5 years ago, # |   -28 Actually, CF does around 7 * 10^7 operations per second. You can see this by submitting this code into the 'Run' tab: #include #include #include 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)
•  » » 5 years ago, # ^ |   +1 OFT,I just know about -O2 optimization yesterday ‪#‎include‬ 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.
•  » » » 5 years ago, # ^ |   +8 However, this code doesn't: #include 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)
•  » » 5 years ago, # ^ |   +20 clock() is very slow, you'd better not call it in the bottleneck. For example, the following code: #include 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.
•  » » » 5 years ago, # ^ |   -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 ??
•  » » » » 5 years ago, # ^ |   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).
•  » » 5 years ago, # ^ |   +6 #include #include #include using namespace std; int main() { int cnt = 0; while (cnt % 1000 || clock() < 1000) ++cnt; cout << cnt << "\n"; } Output: 435594000All I want to say is that clock() is very expensive, so you example is incorrect :)
•  » » » 5 years ago, # ^ |   0 Oh, that's interesting, didn't know about that. Thanks :)
•  » » » 5 years ago, # ^ | ← 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
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Thanks for poining that clock() is too slow.Btw does anyone know, how to override compilation flags from the program?
•  » » » 5 years ago, # ^ |   +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)
•  » » » » 5 years ago, # ^ |   +19 It's possible for GCC options that begin with -O or -f: #pragma GCC optimize("O3 strict-aliasing")
 » 5 years ago, # |   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.
 » 9 months ago, # |   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
•  » » 9 months ago, # ^ |   +1 4 years ago