### Erfan.aa's blog

By Erfan.aa, 8 years ago,

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?

• +12

 » 8 years ago, # |   +1 What's your hacking test?
 » 8 years ago, # |   0 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)
 » 8 years ago, # | ← Rev. 3 →   +4 the c++ compiler made an optimization i guess. i compiled the code without any optimization an it fails (TLE). TEST CASE 300000 1000000000 ... 1000000000 
 » 8 years ago, # |   +3 I think it's because of compiler's optimizer (-O2 option). Think it's called "Loop-dead optimiztion". (Sorry for my poor english)
•  » » 8 years ago, # ^ |   0 Thank you. Do you know what it is, exactly?I guess it increases those "while"s speed.
•  » » » 8 years ago, # ^ | ← Rev. 3 →   -7 I don't think it's because of increasing while speedThis 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.
•  » » » » 8 years ago, # ^ | ← Rev. 4 →   +3 Could you please introduce a good reference about instruction pipelines?Suppose your code is this: long long i = 0, j = 0; while (i < 1000000000) { i++; j += i; } So you mean g++ do j += (long long)1000000001 * 1000000000 / 2; instead of 10^9 jobs?I'd really appreciate your help Ali! ;)
•  » » » » » 8 years ago, # ^ | ← Rev. 4 →   0 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.322swith O2 flag : 0.004sSo, what do you think? Can my system perform 10^9 jobs in 4ms ?
•  » » » » » » 8 years ago, # ^ |   0 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!
 » 8 years ago, # | ← Rev. 2 →   +1 Interesting, a MS Visual Studio compiler doesn't do such optimization even with /O2 and the code gets TLE.
 » 8 years ago, # |   0 It is not a bug. If you compile with -O2 option, gcc optimizes increment operations as in this submission. Consider the code below int i; int j = 0; for (i = 0; i<10; i++) j++; return j; 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 j += 1 type increment operations but not for j += i 
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 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.