Problem Statement
You have a decorative cyclic chain. The chain consists of N gold links, numbered from 1 to N in order.
(For each i between 1 and N-1, inclusive, links i and i+1 are connected. Links 1 and N are also connected. No other pairs of links are connected. )
All links in the chain are mutually distinct - each has its own specific decoration - so you can tell them all apart.
Below we will sometimes use dashes between link numbers to describe specific cyclic chains. For example, the chain -4-7-1-2-3-6-5- is a cyclic chain in which the pairs of links (4,7), (7,1), (1,2), (2,3), (3,6), (6,5), and (5,4) are connected.
A goldsmith knows a careful way to open the links and close them again. This operation can be used to disconnect some pairs of links and later to connect other pairs of links. (Note that you do not need to open both links in a pair to disconnect them - opening one of them is sufficient.)
People often approach the goldsmith with their decorative chains and they ask him to rearrange the links into a different cyclic order. Opening and closing the links wears them out and risks damaging the chain, therefore the goldsmith always tries to minimize the number of such operations.
We are now interested in an obvious question: what is the worst cyclic order people can ask for?
More precisely, your task is as follows. First, find the smallest possible integer K such that the chain you have can be rearranged into any other cyclic chain of N links by opening and later closing at most K links. Second, find one cyclic chain C that cannot be produced from your chain -1-2-...-N- by opening fewer than K links. (The elements of C are the numbers of the links in one possible order along the chain.)
Return a
Definition
- Class:
- RearrangingChains
- Method:
- solve
- Parameters:
- int
- Returns:
- int[]
- Method signature:
- int[] solve(int N)
- (be sure your method is public)
Notes
- Any valid answer (i.e., the correct optimal K followed by any valid permutation of links) will be accepted.
Constraints
- N will be between 3 and 32, inclusive.
Examples
4
Returns: {2, 3, 4, 2, 1 }
The return value claims that K = 2 and that the cyclic chain -3-4-2-1- cannot be produced from the cyclic chain -1-2-3-4- by opening fewer than two links. The second claim can be proved by trying all possibilities which single link to open in the -1-2-3-4- chain. In each of them you will still have a connected pair of links that should not be connected in the desired new chain. E.g., if you open the link 3, links 1 and 4 are still connected. The first claim can be proved by observing that in any chain that consists of these four links the link 1 has two neighbors, and at least one of them must be from the set {2, 3}. Pick one such neighbor and call it x. You can then leave the links 1 and x unopened. Opening the other two links is enough to rearrange the original chain into the desired one.
5
Returns: {4, 5, 2, 4, 1, 3 }
6
Returns: {4, 6, 5, 2, 4, 1, 3 }
The return value claims that K = 4 and that the cyclic chain -6-5-2-4-1-3- is one of the chains that are hardest to produce from the chain -1-2-3-4-5-6-, requiring us to open at least 4 links. It's easy to verify that we can produce the returned cyclic chain by opening exactly 4 links: we can open links 1, 2, 3, 4, rearrange all links into their new order, and then close the links 1, 2, 3, 4 so that each becomes connected with its two new neighbors. If you wanted to make sure that this return value is correct, you would need to show two more things: First, that -6-5-2-4-1-3- cannot be produced from -1-2-3-4-5-6- by opening fewer than three links, and second, that for N=6 there isn't any other cyclic chain that requires us to open more than four links when producing it from -1-2-3-4-5-6-.
3
Returns: {0, 1, 2, 3 }
7
Returns: {5, 4, 1, 6, 3, 5, 7, 2 }
8
Returns: {6, 2, 4, 1, 3, 6, 8, 5, 7 }
9
Returns: {6, 2, 4, 1, 3, 6, 8, 5, 7, 9 }
10
Returns: {7, 2, 4, 1, 3, 6, 8, 10, 7, 5, 9 }
11
Returns: {8, 2, 4, 1, 3, 6, 11, 5, 8, 10, 7, 9 }
12
Returns: {9, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11 }
13
Returns: {9, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 13 }
14
Returns: {10, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 14, 11, 9, 13 }
15
Returns: {11, 2, 4, 1, 3, 6, 8, 5, 7, 10, 15, 9, 12, 14, 11, 13 }
16
Returns: {12, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15 }
17
Returns: {12, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 17 }
18
Returns: {13, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 18, 15, 13, 17 }
19
Returns: {14, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 19, 13, 16, 18, 15, 17 }
20
Returns: {15, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19 }
21
Returns: {15, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 21 }
22
Returns: {16, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 22, 19, 17, 21 }
23
Returns: {17, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 23, 17, 20, 22, 19, 21 }
24
Returns: {18, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23 }
25
Returns: {18, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 25 }
26
Returns: {19, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 26, 23, 21, 25 }
27
Returns: {20, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 27, 21, 24, 26, 23, 25 }
28
Returns: {21, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 26, 28, 25, 27 }
29
Returns: {21, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 26, 28, 25, 27, 29 }
30
Returns: {22, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 26, 28, 30, 27, 25, 29 }
31
Returns: {23, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 26, 31, 25, 28, 30, 27, 29 }
32
Returns: {24, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 26, 28, 25, 27, 30, 32, 29, 31 }
33
Returns: {24, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 26, 28, 25, 27, 30, 32, 29, 31, 33 }
34
Returns: {25, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 26, 28, 25, 27, 30, 32, 34, 31, 29, 33 }
35
Returns: {26, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 26, 28, 25, 27, 30, 35, 29, 32, 34, 31, 33 }
36
Returns: {27, 2, 4, 1, 3, 6, 8, 5, 7, 10, 12, 9, 11, 14, 16, 13, 15, 18, 20, 17, 19, 22, 24, 21, 23, 26, 28, 25, 27, 30, 32, 29, 31, 34, 36, 33, 35 }