Erfan.aa's blog

By Erfan.aa, 11 years ago, In English

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?

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

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What's your hacking test?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

»
11 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

the c++ compiler made an optimization i guess. i compiled the code without any optimization an it fails (TLE).

TEST CASE
300000
1000000000 ... 1000000000
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think it's because of compiler's optimizer (-O2 option). Think it's called "Loop-dead optimiztion". (Sorry for my poor english)

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

    Thank you. Do you know what it is, exactly?

    I guess it increases those "while"s speed.

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 3   Vote: I like it -7 Vote: I do not like it

      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.

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 4   Vote: I like it +3 Vote: I do not like it

        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! ;)

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          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 ?

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

            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!

»
11 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Interesting, a MS Visual Studio compiler doesn't do such optimization even with /O2 and the code gets TLE.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.