Editorial for Wesley's Anger Contest 5 Problem 1 - Matryoshka Acorns


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.

Author: Pookmeister

Subtask 1

We note that with acorns of only sizes 1 and 2, each acorn of size 1 can be nested inside a single acorn of size 2 and each acorn of size 2 cannot be nested in any other acorn. It is always optimal to place an acorn of size 1 inside an acorn of size 2 if they do not already contain an acorn of size 1, since any other acorn that could be nested would also be of size 1.

Time Complexity: \mathcal O(N)

Subtask 2

For full points, we notice that it is optimal to nest as many acorns as possible. By processing the acorns in non-decreasing order, we know that for any acorn of size i it can be nested in any acorn of at least size i+1.

We also observe that it is optimal for an acorn of size i to have the largest acorn that is at least as small as size i-1 to be nested inside it.

Thus for every acorn being processed we can add it to some container, then we can remove the largest acorn that is smaller than the current acorn being processed from the container, if one exists.

Time Complexity: \mathcal O(N^2) or \mathcal O(N \log N)

Bonus: There's also a \mathcal O(N+\max(a_i)) solution.


Comments

There are no comments at the moment.