Wrong OBI's solution and consequently I/O too
feodorv asked 5 months ago
Alas, the official OBI's solution (used to generate judge output) is wrong. It's algorithm uses URI 1683 (Largest Rectangle in a Histogram) as a subproblem but does not check that the height shouldn't be zero:
if( h[ptr-1] > 0 ) // <-- absent ret = max(ret, (i-s[ptr-1]+1) * (h[ptr-1]+1));
For URI 1683 the multiplication by zero gives zero with no consequences. Here we add 1 to zero and consequently get non zero value which compare with the final result. For example the following input
2 7 1 1 1 1 1 0 1 1 0 1 1 1 1 1
produces the unreal answer 7 - the answer for the input must be even!!!
This topic has not been answered yet. Be the first!