Блог пользователя Erfan.aa

Автор Erfan.aa, 11 лет назад, По-английски

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
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What's your hacking test?

»
11 лет назад, # |
  Проголосовать: нравится 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)

»
11 лет назад, # |
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
»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

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

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

    I guess it increases those "while"s speed.

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится -7 Проголосовать: не нравится

      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 лет назад, # ^ |
        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! ;)

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          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.322s

          with O2 flag : 0.004s

          So, what do you think? Can my system perform 10^9 jobs in 4ms ?

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится 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!

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится 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
  • »
    »
    11 лет назад, # ^ |
    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.