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.
The quantity
m[i - 1]is undefined wheni=0. The ternary operator ensures that this undefined value is not used by checking ifiis nonzero.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#55I think the TLE is occurring because you are using
memset(mem, -1, sizeof(mem)). Usingmemsetwill set the byte of each one to -1, so you will not end up with -1 in each cell, but something like10000000100000001000000010000000instead. 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.
memsetwith -1 is perfectly fine -- the bit pattern of -1 is all ones.ah yes, it looks like my C++ knowledge is still lacking, thank you for the clarification!
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 thensolveuses this for prefix sums --a[i] + ... + a[j]=m[j] - m[i-1](the random value coming fromm[-1]cancels out). Essentially it implements prefix sums without branching and with an array of only sizen.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
mbe of sizen+1and move each entry up one step, presumably settingm[0] = 0.