Laggy's blog

Just found an OP UB!
By Laggy, history, 7 years ago, In English

Problem: 467C - George and Job So as you can see this is so cool because the bug doesn't actually have anything to do with the solving function. It happens somewhere when building the prefix sum. The current code doesn't pass TC#5 while after removing the green part it goes up to TC#55. How? I wish I knew. Maybe you guys have some thoughts ^^

Kudos to Bassel for playing with it.

Tags bug, op
  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The quantity m[i - 1] is undefined when i=0. The ternary operator ensures that this undefined value is not used by checking if i is nonzero.

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

    that's not what he's saying, he's saying that without the ternary operator it passes more cases.

    The current code doesn't pass TC#5 while after removing the green part it goes up to TC#55

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

I think the TLE is occurring because you are using memset(mem, -1, sizeof(mem)). Using memset will set the byte of each one to -1, so you will not end up with -1 in each cell, but something like 10000000100000001000000010000000 instead. That is why you are getting TLE, because it's recalculating each time.

UPD: that, and I think that your algorithm is N^3 = TLE.

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

    memset with -1 is perfectly fine -- the bit pattern of -1 is all ones.

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

      ah yes, it looks like my C++ knowledge is still lacking, thank you for the clarification!

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

This is pretty neat. The code without the green parts computes m[-1] = nonsense, m[0] = nonsense + a[0], m[1] = nonsense + a[0] + a[1], etc., and then solve uses this for prefix sums -- a[i] + ... + a[j] = m[j] - m[i-1] (the random value coming from m[-1] cancels out). Essentially it implements prefix sums without branching and with an array of only size n.

It's wildly undefined behavior, of course, and it would not be surprising if a compiler noticed that and e.g. optimized away certain loop iterations. (It would also crash if you compiled your program with ASan and UBSan, which I highly recommend.) Simplest fix would be to make m be of size n+1 and move each entry up one step, presumably setting m[0] = 0.

→ Reply