Editorial for COCI '09 Contest 2 #6 Pasijans
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 and , both share the same prefix of length . Let the card in deck have a smaller value than the card in deck . It is preferential for us to choose deck over deck because when at some point we remove those cards, if we chose deck we get worse results than if we chose deck . Because those 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 . There are at most of these. We sort these and use this info for fast comparison. Suppose we sorted all substring of length . It is clear that a sequence of length is formed by connecting two sequences of length . We now have a simple way to check for ordering of two strings of length . We compare the first halves, and if needed second halves. The complexity of using such a comparison of the greedy strategy is .
Comments