Scribd
Upload
6 views2 pages

Lexicographic Permutations for Skew Heaps

The document describes a problem involving skew heaps, where students must determine if a given heap can be produced by a specific insertion method and find the lexicographically minimal and maximal input permutations. It outlines the structure of a skew heap and provides input and output formats, including sample inputs and their corresponding outputs. The problem is set within the context of a homework assignment by Professor Taylor Swift, and it includes constraints on the number of nodes and the tree structure.

Uploaded by

akshita.m2015
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views2 pages

Lexicographic Permutations for Skew Heaps

The document describes a problem involving skew heaps, where students must determine if a given heap can be produced by a specific insertion method and find the lexicographically minimal and maximal input permutations. It outlines the structure of a skew heap and provides input and output formats, including sample inputs and their corresponding outputs. The problem is set within the context of a homework assignment by Professor Taylor Swift, and it includes constraints on the number of nodes and the tree structure.

Uploaded by

akshita.m2015
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Problem A

A-Skew-ed Reasoning
Time limit: 2 seconds
The following is based on a true story – the names have been changed because. . . well, because you
always change names in stories like this one.
Professor Taylor Swift is grading a homework assignment on integer skew heaps. A skew heap is a
binary tree with an integer stored in each node such that the value in any node is less than or equal to the
values in any of its children. Note that the skew heap need not be a perfect binary tree; that is, the left
and/or right subtree of any node may be empty.
Inserting a value x into a skew heap H is done using the following recursive procedure:

• If H is empty, make H a skew heap consisting of a single node containing x.


• Otherwise, let y be the value in the root of H.
– If y < x, swap the two children of the root and recursively insert x into the new left subtree.
– If y ≥ x, create a new node with value x and make H the left subtree of this node.

4 4

9 5 5 9

20 25 6 11 7 6 20 25

17 11

17

Figure A.1: Example of inserting the value 7 into a skew heap. The nodes storing 4 and 5
(marked in blue) have their children swapped, while the node storing 11 becomes the left
child of the newly inserted node (marked in red).

Now, back to Professor Swift. The homework problem she has assigned asks the students to show the
heap that results from inserting a given permutation of the numbers from 1 to n, in the given order,
into an empty heap. Surprisingly, some of the students have wrong answers! That got Professor Swift
wondering: For a given heap, is there an input permutation that would have produced this heap? And if
so, what are the lexicographically minimal and maximal such input permutations?

Input

The first line of input contains an integer n (1 ≤ n ≤ 2 · 105 ), the number of nodes in the tree. These
nodes contain the numbers from 1 to n exactly. This is followed by n lines, the ith of which contains
two integers ℓi and ri (i < ℓi ≤ n or ℓi = 0; i < ri ≤ n or ri = 0), describing the values of the left and
right children of the node storing i, where a value of 0 is used to indicate that the corresponding child
does not exist. It is guaranteed that this data describes a binary tree.

49th ICPC World Championship Problem A: A-Skew-ed Reasoning © ICPC Foundation 1


Output

Output the lexicographically minimal input permutation that produces the given tree under the insertion
method for skew heaps, followed by the lexicographically maximal such input permutation. These per-
mutations may coincide, in which case you still need to output both. If no input permutation producing
the given tree exists, output impossible.

Sample Input 1 Sample Output 1


7 1 3 2 7 5 6 4
2 3 7 1 5 3 2 6 4
4 5
6 7
0 0
0 0
0 0
0 0

Sample Input 2 Sample Output 2


2 impossible
0 2
0 0

Sample Input 3 Sample Output 3


3 2 3 1
2 0 3 2 1
3 0
0 0

49th ICPC World Championship Problem A: A-Skew-ed Reasoning © ICPC Foundation 2

You might also like