Editorial for WC '17 Contest 4 S3 - Guardians of the Cash


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.

Let A1N be the Southern skyline, and B1N be the Western skyline. Let Mi=min{Ai,Bi}. All 2N1 stacks in row i and column i must be pruned down to a height of at most Mi. Let's refer to this reduction of stacks as "processing index i". Note that it's not a simple matter of processing each index between 1 and N. When an index is processed, it may affect the heights of stacks in other rows/columns, which may affect other A, B, and M values.

This may suggest the following approach: Process all of the indices, then process them all again, and so on until a full iteration of processing all N indices results in no further changes to the collection of coins. Processing a single index takes O(N) time, and it can be shown that this algorithm will terminate within O(N) iterations of processing all N indices, resulting in a time complexity of O(N3). Processing the indices in random orders may be tempting, but the time complexity will remain at O(N3), and sufficiently strong test data can be constructed such that the algorithm will require roughly N/2 iterations.

A key observation is that, when an index i is processed, it can only affect the M values of other indices j when Mj>Mi. Furthermore, when such an index j is affected, its M value may be reduced down to Mi, but not lower than that. This suggests that, if we process all N indices in non-decreasing order of M, the M values of already-processed indices will never be affected, and so a single iteration through all N indices will be sufficient.

That being said, it's insufficient to sort all N indices by their initial M values and process them in that static order, as their M values can change during the algorithm, which may change the order in which they should be processed. Therefore, we'll need to dynamically keep track of the A, B, and M values. At each step of the algorithm, we'll choose to process the remaining unprocessed index with the minimum M value (in a fashion reminiscent of Dijkstra's shortest path algorithm). While processing an index, we'll then need to update other A, B, and M values more efficiently than iterating over all O(N2) stacks in the grid. Overall, it's possible to implement this approach in time O(N2logN), for example by maintaining a set (balanced binary search tree) of pairs {Mi,i} as well as a multiset of C values for each row and each column.


Comments

There are no comments at the moment.