Hey guys! I've found something strange about the Codeforces judge. Please read this submission: 3373203 (for problem C) (with n <= 3 * 10^5 and -10^9 <= a[i] <= 10^9)
I think the verdict for this submission should be "TLE" because of its O(answer) algorithm. Answer for this problem can be as large as 10^13. (During the contest, I hacked this submission twice and got "Unsuccessful hacking attempt" (and -100 points!))
Am I wrong? Is the code judged correctly?
What's your hacking test?
Give us your test, or generator... Maybe it's wrong? I don't think, that codeforces has such bug... P.S I agree with you and think, that that solve works O(answer)
the c++ compiler made an optimization i guess. i compiled the code without any optimization an it fails (TLE).
I think it's because of compiler's optimizer (-O2 option). Think it's called "Loop-dead optimiztion". (Sorry for my poor english)
Thank you. Do you know what it is, exactly?
I guess it increases those "while"s speed.
I don't think it's because of increasing while speed
This is because of instruction scheduling that is what -O2 flag does ( Read about instruction pipelines ) In this case I think -O2 flag, causes the while to run all of the steps at once.
Could you please introduce a good reference about instruction pipelines?
Suppose your code is this:
So you mean g++ do j += (long long)1000000001 * 1000000000 / 2; instead of 10^9 jobs?
I'd really appreciate your help Ali! ;)
I'm not a g++ developer ;) I think what you want is "Scheduling Algorithms" and I suggest you to read Scheduling Algorithms, Peter Brucker.
But about this code, I have tested it, it's the result by time:
without O2 flag : 2.322s
with O2 flag : 0.004s
So, what do you think? Can my system perform 10^9 jobs in 4ms ?
It's so clear that a CPU with (eg.) 2 GHz clock can do 2 * 10^9 jobs a second. So it's impossible to do 10^9 jobs in 0.004s...
This little time must be spent only for determining the "loop's result" I guess!
Interesting, a MS Visual Studio compiler doesn't do such optimization even with /O2 and the code gets TLE.
It is not a bug. If you compile with -O2 option, gcc optimizes increment operations as in this submission.
Consider the code below
If you look the generated assembly code (with -S option), compiler precalculates and returns the value (10, in this case) immediately.
This optimization is applied also for
type increment operations but not for
I think you are wrong.
In your code change types to long long int and then instead of 10 place an attribute named "n" and get it from user in the first, then test the time, you cannot see any special thing in assembly code, if you read about O2 flag, it brings Instruction Scheduling that has many algorithms.