justarandomstring's blog

How can the same code gap be so great?
By justarandomstring, history, 7 years ago, In English

It wasn't the first or second time I had this problem, so I couldn't help asking what was going on.

Today, I had a strange problem when I submitted this question 600E - Lomsat gelral

First, I submitted this code:

The full code is here: My TLE code

// ...Omitted...
long long Sum, v[MAXN], ans[MAXN];
// ...Omitted...

and got TLE(used more than 2000ms).

After a long inspection, I didn't find any problems, so I wrote it again. The new code is:

The full code is here: My AC code

// ...Omitted...
long long ans[MAXN], v[MAXN], Sum;
// ...Omitted...

ans got AC(only used 140ms).

The omission of the two code is exactly the same, and the result is too different!

I wonder what really happened.

Thanks.

Tags c++
  • Vote: I like it
  • +79
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

i also remember that once, my teammate and i were solving some problem.
one submission got ac in ~3000ms another submit for the same code got ac in ~2000. they both were ac but time difference was more than 1 second which is quit big.

i wanted to investigate the problem but didn't. my guess was that it is due to old and new servers of codeforces.

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

    I have submitted more than five times and got the same result. So I think it is not because of the server's age. I'm very curious about the reason.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did you try to create your own tests and see if it is same on your machine as well?

→ Reply
»
7 years ago, # |
  Vote: I like it +27 Vote: I do not like it

It seems to me that in line 26 or 28 you may be accessing negative index of array. If this happens to be v[-1] then you are overwriting variable Sum (in first case) which may cause problems later, that are not present when you change variable order.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Before line 26 and 28, I added this: assert(times >= 0); and the full code after changing is here. The reuslt is still TLE rather RE, so I think it shouldn't be this reason maybe.

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

      Maybe what he's trying to say is, when you access v[-1], the code will access the memory right before the initial part of the array v. So it access the variable Sum.

      You didn't just change the order of the variable Sum, you also placed the ans array before v array.

      I've submitted your code in the following order:

      long long Sum, ans[MAXN], v[MAXN];

      And it passed with 639 ms

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How you can find your mistake ? ))

→ Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

This line might fail (Max going below 0): while(!v[Max]) Max--;

→ Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +50 Vote: I do not like it

As ania and Sazzon suggested and as it usually happens, your code invokes undefined behavior. It happens even on the first sample test case in line 30:

  while(!v[Max]) Max--;

Here, Max variable can become less than zero. I don't really know what this variable is about, but if I add assert(Max >= 0); in the end of loop's iteration, it fails. Meaning, your code can behave in arbitrary way depending on anything, including but not limited to current moon phase. In particular, it can enter an infinite loop.

Please do not try to argue why the code should still work. Compiler is allowed to do anything, and it frequently does really "strange" and "unexpected" things.

→ Reply