Editorial for COCI '09 Contest 2 #6 Pasijans


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 us try to form a greedy strategy. The question we need to answer is, what deck do we take the card to form the best solution sequence? Let's examine all top cards on all decks. If there is only one smallest card, it is obvious we need to choose that deck. Any other deck yields worse solution sequences. The problem is if more than one deck shares the smallest card. We now examine the prefixes of those decks. For simplicity, we only present a case with two decks. Extension to more decks is simple. Let's examine decks A and B, both share the same prefix of length L. Let the L+1 card in deck A have a smaller value than the L+1 card in deck B. It is preferential for us to choose deck A over deck B because when at some point we remove those L cards, if we chose deck B we get worse results than if we chose deck A. Because those L cards are equal, it is irrelevant what deck we choose up to that point. If one of the decks is a full prefix of the other, we choose the one with the larger length. This gives us a greedy strategy to work with. We just need a data structure that can quickly maintain this greedy ordering. Let us examine all substrings of all decks of length 2d. There are at most 1000N of these. We sort these and use this info for fast comparison. Suppose we sorted all substring of length 2d-1. It is clear that a sequence of length 2d is formed by connecting two sequences of length 2d-1. We now have a simple way to check for ordering of two strings of length 2d. We compare the first halves, and if needed second halves. The complexity of using such a comparison of the greedy strategy is \mathcal O(N \log^2 N).


Comments

There are no comments at the moment.