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!

Remember not post solutions. Your post may be reviewed by our moderators.