rumike's blog

By rumike, history, 5 months ago, In English

I was resolving 1922D - Berserk Monsters, and I found that access to the prev of beginning of set doesn't through wrong answer and can't get why.

First as you can see in that sumbmission that give wrong answer 264232760, I put the defense of border element at N = 2e9 + 5, and their attacks at 0 so they can't die neither attack. I took that value because 2*1e9 < N.

But in the editorial they took INT_MAX which is 2147483647 and it worked as you see here 264232643. I could not get why it's working, and after some times, I remark that if for the example the border 0 is in live set, it would be at the beginning of the set, and the code tried to access to predecessor of it, after and got the predecessor, it use that value as array index, which would normally leads to runtime error, but I get it gave a value which can be more than 1e9, it's for that reason N = 2e9 + 5 is not sufficient to prevent border to die.

Can someone explain why predecessor of the beginning of a set doesn't lead to runtime error, and why it's work?

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