A Fitting Advertisement

Problem E - A Fitting Advertisement

It wouldn't be an SPP ACM Regional without its fair share of bugs, and this problem provided them for us. Given a histogram (i.e. heights across X value), find whether rectangles fit inside it.
Sounds simple, with small catches - the heights can be zero, though that changes not much, and it doesn't matter which orientation you have for the rectangle, though again, you can just treat it as two different rectangles, and OR the results together, not too bad.

Ok, so as submissions come in, people whose code looks right are failing. A bit of testing by the judges leads to the discovery that some of the rectangles you are placing have their width (or height) zero, which is explicitly disallowed in the problem specification. What's more, it's hard to know when a zero-sized rectangle fits within the histogram - the most 'logical' to me would be that it always fits, as it has zero area, yet the official judgement was different.

Here's where problem 2 lies - Rather than removing zero-area rectangles from the input, so that contestants would only have to solve the problem they were given, it was for some reason decided that the problematic input would be kept, and instead the question changed, the changes then had to be broadcast to all contestants. weird :S

Oh, and to make it a bit worse, no limits were placed on how many rectangle queries there were. This does make a difference, as if there are many per histogram, it's best to pre-process the grid in O(400*1000) then solve each query in O(1). However, I'm guessing the number of queries is low, so instead, an algorithm that should work (though is as yet un-judged) is:
For each X-by-Y rectangle, see if it fits either normally or rotated as a Y-by-X rectangle

To check if an A-by-B rectangle fits under the histogram -
find the longest section with height >= A, and the longest section with height >= B in linear time.
If the former is >= B, or the latter is >= A, the rectangle fits.
This gives a complexity of O(#queries * width of histogram) and quite small to code - implementation can be found here.