Editorial for DMOPC '18 Contest 6 P5 - Quadrat Sampling


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: AvaLovelace

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 \displaystyle  \sum_{i = 1}^K \max(cnt[a_i + j][b_i], cnt[a_i][b_i + j]),\ j \in [-T, T]~ where cnt[a][b] is the number of quadrats covering the cell at row a and column b.

For the first subtask, we can use a 2D prefix sum array to compute all cnt[a][b] in \mathcal O(1) per quadrat plus \mathcal O(NM) post-processing. Then, for each goose, we can go over all the \mathcal O(T) cells that it can reach to find the one covered by the most quadrats.

Time complexity: \mathcal O(NM + Q + KT)

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 i, we add 1 to or subtract 1 from the cells from c_{1i} to c_{2i}. When we reach goose i, we query the cells from b_i - T to b_i + T to find its \max(cnt[a_i][b_i + j]).

We can then do a similar sweep from left to right to find \max(cnt[a_i + j][b_i]) for each goose.

Time complexity: \mathcal O(N + M + (K + Q)(\log N + \log M))

For the final subtask, we must first compress the coordinates so that the maximum row and column are \mathcal O(K + Q). Then, we can do the same thing as in the second subtask.

Time complexity: \mathcal O((K + Q)\log (K + Q))


Comments

There are no comments at the moment.