Editorial for DMOPC '18 Contest 6 P5 - Quadrat Sampling
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
In order to maximize the raw total, each goose should fly to a cell covered by as many quadrats as possible so that it can be counted the maximum number of times. Thus, we seek
where
is the number of quadrats covering the cell at row
and column
.
For the first subtask, we can use a 2D prefix sum array to compute all in
per quadrat plus
post-processing. Then, for each goose, we can go over all the
cells that it can reach to find the one covered by the most quadrats.
Time complexity:
For the second subtask, we can sweep the rows from top to bottom, keeping a data structure such as a segment tree that allows for efficient range addition updates and range maximum queries. When we reach the beginning or the end of quadrat , we add 1 to or subtract 1 from the cells from
to
. When we reach goose
, we query the cells from
to
to find its
.
We can then do a similar sweep from left to right to find for each goose.
Time complexity:
For the final subtask, we must first compress the coordinates so that the maximum row and column are . Then, we can do the same thing as in the second subtask.
Time complexity:
Comments