← All solutions

Solved by 45 teams.

First solved after 73 minutes.

Shortest judge solution: 1197 bytes.

We can find the desired input sequences by traversing the tree recursively. Suppose we are in the root node 1 and we want to find out where in the input sequence the 1 can be placed. Based on the insertion method for skew heaps we know that everything after the 1 alternates between going to the left and right subtrees, while everything before the root must have gone either entirely into the left subtree or entirely into the right subtree, depending on the parity of the root position. This means that we can compute the possible positions of the root based on the sizes of its left and right subtree, and it turns out that there are always between 0 and 2 of them. Additionally, the case where there are two positions only happens if these two positions are exactly the first two positions in the sequences, so that we clearly want to use the first for constructing the lexicographically minimal sequence and the second for constructing the lexicographically maximal sequence. In both cases, we recursively descend into the two subtrees, construct the respective minimal and maximal sequences for those, and then merge them based on the observations we’ve made.

As there are up to 2 · 10⁵ nodes in the tree, some care needs to be taken to construct the sequences fast enough. To this end we may notice that combining the sequences for the left and right subtrees amounts to interleaving the shorter sequence into an equal-length suffix of the longer sequence, so that this process only takes time proportional to the length of the shorter sequence. The overall time is therefore O(n · log(n)), because every element can only belong to the shorter sequence of a merge a logarithmic number of times.