Editorial for COI '08 #3 Plahte
Submitting an official solution before solving the problem yourself is a bannable offence.
Consider one of the sheets and how the area of stained fabric in it changes over time. Analysing various cases we can see that, if squares of fabric are initially stained when the oil front hits, then
squares will be stained after a second,
after two seconds etc. where
can be zero, two or four. This continues until the entire width or height of the rectangle is stained, after which one additional row or column gets stained per second (we can also recalculate
at that point and change
to zero).
One efficient solution calculates the important time points (events), in which and
for a sheet change. The time complexity of this part is
. Then we simulate second by second and, using the known data about
and
for every rectangle, we can calculate the change of area of stained fabric in
per second.
An alternative approach is to first fold all rectangles into the first quadrant. Then we can represent every rectangle as a combination of four quarter-planes extending up and right (inclusion-exclusion principle) and, similar as before, calculate the change of area of stained fabric in each quarter-plane. Representing rectangles as quarter-planes reduces the number of special cases our implementation needs to handle.
Comments