← All solutions

Shortest judge solution: 1756 bytes. Shortest team solution (during contest): 1576 bytes.

Fun fact: this problem was originally in the reverse direction, so the description of the solution below is “backwards” from the point of view of the problem, but this does not really change anything.

We have two copies of a string of characters (only three different characters appear, but we will not use this fact in our solutions). We want to subsequently remove characters from the copies, so that all of the strings given on the input appear in one of the copies during the process.

In graph-theoretic terms, we have a directed acyclic graph (the strings being the vertices, and an edge from string A to string B if B is a subsequence of A), and we would like to know if there are two paths, each starting at the base string, that together cover all vertices.¹

Like most problems on DAGs, this has a relatively standard dynamic programming solution, in this case with running time O(N²). There is a catch however: a naive way of creating the graph takes time Ω(N²S) (comparing all ≈ N²/2 pairs of strings to each other, each for Ω(S) time). So we have to be a bit more clever, and in fact, once one understands the problem well enough to construct the graph more quickly, it turns out that the problem admits a simple greedy solution.

First, note that a topological sort of the graph can be obtained by sorting the strings by decreasing length (which can be done in O(NS + N log N) time). Now we go through the strings in topological order. At each step, we consider pairs of decreasing sequences that both start with the base sequence and then use the first k elements of the topologically sorted sequence. We only care about the last string of each sequence (as they are the only ones we have to compare the next string to). We will show there are at most two pairs of strings we need to consider as “possible lasts”. Furthermore, if there are two of them, they have a special structure: they share an element, and this shared element is smaller then the other two elements in the pairs. I.e., they are of the form (A, B) and (A, C), where A ≤ B and A ≤ C.

¹ In combinatorial terms, we’d like to know if a given poset can be covered by two chains. By Dilworth’s Theorem, this is equivalent to asking if the width of the poset is ≤ 2. But while this is something everyone should know, it is irrelevant for this particular problem.

Initially we have a single pair – the two base strings. In each step we add another string, and we want to append it to one of the sequences. We consider two cases.

Case 1: a single candidate If we currently have a single candidate pair of sequences, we have to append our new string to one of the elements of the pair. Depending on whether this can be done in 0, 1, or 2 different ways, we get 0, 1, or 2 different new candidate pairs (in the case of 0, answer is impossible, and in the case of 2, note that the two candidate pairs have the special structure described above).

Case 2: two candidate pairs We have two candidate pairs (A, B) and (A, C), and we try to add a new element D. If D ≤ A, we can replace any string by D, nominally giving the three candidates (D, A), (D, B), and (D, C). However, the pair (D, A) is redundant – since A ≤ B, any completion of (D, A) to a full solution is a valid completion of (D, B) as well.

If D cannot be appended to A, then we will have a sequence ending with A and a sequence ending with D — thus we have only one pair (D, A) of possible sequence ends.

To check if this is indeed possible, we have to compare D to B and C, and if it can be appended to either of them, (D, A) becomes our candidate pair, while otherwise we return impossible.

This algorithm obviously makes a constant number of comparisons (2.5 comparisons per step, for we can make three comparisons only every second step), so it runs in a total time O(NS).