Problem Statement
A Skolem sequence of order n is a sequence of length 2n that contains each of the numbers 1, 2, ..., n exactly twice and has the following property:
for each i, the distance between the two copies of the number i is exactly i.
(The distance is measured as the difference between their indices.)
For example, {1, 1, 3, 4, 2, 3, 2, 4} is a Skolem sequence of order 4. You may note that the 1s are at distance 1 from each other, the 2s are at distance 2, and so on.
For some values of n, there is no Skolem sequence of order n. For example, there is no Skolem sequence of order 3. That's why we decided to look at a more general class of objects: Skolem binary trees.
A Skolem binary tree of order n is a binary tree that contains exactly 2n nodes. Each node contains a positive integers. Among those integers, each of the numbers 1, 2, ..., n occurs exactly twice. Additionally, for each i, the distance between the two nodes that contain the number i must be exactly i.
For example, this is a valid Skolem binary tree of order 3:
It is guaranteed that there is always a solution. If there are multiple valid solutions, you may choose any one of them.
For simplicity, we will not care about the way your tree is rooted. This means that you can produce any undirected tree in which each node has degree at most 3. Once you have chosen such a tree, the return value is computed as follows:
For example, {1, 1, 3, 4, 2, 3, 2, 4} is a Skolem sequence of order 4. You may note that the 1s are at distance 1 from each other, the 2s are at distance 2, and so on.
For some values of n, there is no Skolem sequence of order n. For example, there is no Skolem sequence of order 3. That's why we decided to look at a more general class of objects: Skolem binary trees.
A Skolem binary tree of order n is a binary tree that contains exactly 2n nodes. Each node contains a positive integers. Among those integers, each of the numbers 1, 2, ..., n occurs exactly twice. Additionally, for each i, the distance between the two nodes that contain the number i must be exactly i.
For example, this is a valid Skolem binary tree of order 3:
3
/ \
2 2
\
1
/ \
3 1
You are given the int k.
Find and return one possible Skolem binary tree of order k.
It is guaranteed that there is always a solution. If there are multiple valid solutions, you may choose any one of them.
For simplicity, we will not care about the way your tree is rooted. This means that you can produce any undirected tree in which each node has degree at most 3. Once you have chosen such a tree, the return value is computed as follows:
- Label the vertices of your tree 0, 1, ..., 2n-1 in such a way that for each i, the two vertices that contain the number i will get labels 2i-2 and 2i-1.
- Construct a list of edges of your tree: for each edge, in an arbitrary order, list the labels of the two vertices it connects.
- Return that list as a int[] with 2*(2n-1) elements.
Definition
- Class:
- SkolemBinaryTree
- Method:
- construct
- Parameters:
- int
- Returns:
- int[]
- Method signature:
- int[] construct(int k)
- (be sure your method is public)
Constraints
- k will be between 1 and 100, inclusive.
Examples
4
Returns: {0, 1, 1, 5, 5, 6, 6, 2, 2, 4, 4, 3, 3, 7 }The return value describes a tree with the following edges: 0-1, 1-5, 5-6, 6-2, 2-4, 4-3, and 3-7. This tree is a simple path: 0-1-5-6-2-4-3-7. From the labels of its nodes we can derive that the numbers in those nodes are {1, 1, 3, 4, 2, 3, 2, 4}, in this order. This means that this particular Skolem tree corresponds to the Skolem sequence of order 4 shown in the problem statement.3
Returns: {3, 4, 4, 2, 2, 1, 1, 0, 1, 5 }This return value corresponds to the Skolem tree of order 3 shown in the problem statement.5
Returns: {4, 9, 9, 3, 3, 5, 5, 2, 2, 6, 6, 8, 8, 0, 0, 1, 1, 7 }We have a Skolem sequence again: 3-5-2-3-2-4-5-1-1-4.
Back to all problems