TopCoder Statistics - Problem Statement

Problem Statement

You are given a int[] p with n elements. The elements of p form a permutation of {0, 1, ..., n-1}. We want to sort the permutation p into ascending order. We will do so by using a rooted tree with exactly n+1 nodes. The sorting process is described below.

Only some rooted trees can be used to sort p. Different trees may have a different cost (also defined below). Find and return the cost of the cheapest tree that can be used to sort the given permutation p.

Sorting of a permutation using a rooted tree works as follows.

Select a rooted tree with exactly n+1 nodes. (The tree may have an arbitrary shape. In particular, it's not required to be binary.)
Distribute the elements of p onto the n non-root nodes of the tree.
Collect the elements of p from the nodes of the tree, forming a sorted sequence.

When distributing the elements of p onto the nodes of the tree, you must use the following pseudocode:

for each i = 0 .. n-1:
    select a node t other than the root
    t must be such that:
        - all nodes on the path from t to the root, including t itself, are empty
        - all nodes x != t such that t lies on the path from x to the root already have a value
    place the value p[i] onto the node t

After this part, each node other than the root will contain one element of p. When collecting the values from the tree to form the sorted sequence, you must use the following pseudocode:

let R be an empty sequence
for each i = 0 .. n-1:
    select a node t other than the root
    t must be such that:
        - t contains a value
        - all other nodes on the path from t to the root are already empty
    append the value in node t to the sequence R
    remove the value from node t
return R

After this step, all nodes are empty again, and R contains a permutation. The process was successful if and only if R = {0, 1, ..., n-1}.

For example, let p = {1,3,2,0}. We will show that this permutation can be sorted using the following tree (where r is its root):

We can do it like this:

first phase:

    r        r        r        r        r
   / \      / \      / \      / \      / \   
  x   x    1   x    1   x    1   x    1   0 
     / \      / \      / \      / \      / \
    x   x    x   x    3   x    3   2    3   2

second phase:

    r        r        r        r        r
   / \      / \      / \      / \      / \   
  1   0    1   x    x   x    x   x    x   x
     / \      / \      / \      / \      / \
    3   2    3   2    3   2    x   2    x   x

The cost of a rooted tree is the sum of the squares of the degrees of its vertices. For example, the cost of the tree used above is 2^2 + 1^2 + 3^2 + 1^2 + 1^2 = 4+1+9+1+1 = 16.

Given a permutation p, find and return the smallest possible cost of a tree that can be used to sort p.

Definition

Class:: TreeSorter
Method:: minimalCosts
Parameters:: int[]
Returns:: int
Method signature:: int minimalCosts(int[] p)
(be sure your method is public)

Notes

The return value is always defined. In particular, there is always at least one rooted tree that can be used to sort the given permutation: the tree in which the root has degree n.

Constraints

p will contain between 1 and 50 elements, inclusive.
p will be a permutation of 0, 1, 2, ..., (|p|-1).

Examples

{1,3,2,0}

Returns: 14

The tree with cost 16 mentioned in the statement can sort this permutation, but it is not the cheapest tree with this property. An optimal solution is the tree shown below. The cost of this tree is 2^2 + 2^2 + 2^2 + 1^2 + 1^2 = 14. tree: r / \ x x | | x x first phase: r r r r r / \ / \ / \ / \ / \ x x x x x x x 2 0 2 | | | | | | | | | | x x 1 x 1 3 1 3 1 3 second phase: r r r r r / \ / \ / \ / \ / \ 0 2 x 2 x 2 x x x x | | | | | | | | | | 1 3 1 3 x 3 x 3 x x
{0,2,3,1}

Returns: 16

This time the tree with cost 16 that is shown in the problem statement is an optimal solution. r / \ x x / \ x x
{0,1,2,3,4,5,6,7}

Returns: 72

The only possible tree is the tree in which the root has degree 8, and each other node is its child. The cost of this tree is 8^2 + 8 * 1^2 = 72.
{6,5,4,3,2,1,0}

Returns: 26

One optimal solution is a simple path with 8 nodes.
{0}

Returns: 2
{49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

Returns: 198
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49}

Returns: 2550
{43, 4, 40, 44, 35, 36, 34, 20, 31, 42, 38, 22, 15, 13, 23, 33, 48, 30, 1, 14, 8, 12, 27, 39, 21, 11, 17, 10, 47, 3, 2, 46, 45, 16, 18, 7, 41, 0, 37, 9, 32, 24, 49, 26, 29, 25, 19, 28, 5, 6}

Returns: 210
{11, 22, 3, 10, 38, 31, 15, 18, 29, 34, 14, 47, 5, 36, 32, 40, 9, 20, 1, 8, 6, 2, 30, 7, 19, 26, 35, 43, 37, 33, 41, 4, 27, 49, 23, 39, 12, 17, 24, 21, 46, 16, 0, 25, 45, 28, 44, 48, 13, 42}

Returns: 222
{19, 11, 44, 49, 16, 26, 32, 41, 25, 40, 14, 39, 48, 24, 5, 18, 9, 17, 12, 0, 4, 47, 46, 28, 29, 10, 35, 15, 8, 34, 20, 37, 31, 42, 38, 6, 1, 23, 13, 27, 7, 33, 22, 45, 21, 36, 3, 43, 2, 30}

Returns: 216
{28, 29, 30, 2, 38, 10, 39, 25, 37, 16, 22, 3, 13, 19, 36, 20, 17, 7, 21, 35, 47, 42, 8, 32, 34, 0, 33, 4, 31, 15, 18, 40, 45, 27, 23, 9, 44, 24, 14, 48, 43, 12, 46, 11, 26, 49, 41, 6, 5, 1}

Returns: 218
{8, 27, 35, 15, 44, 4, 32, 48, 23, 13, 1, 20, 16, 31, 22, 9, 26, 36, 0, 43, 30, 46, 12, 18, 40, 19, 38, 5, 41, 42, 3, 37, 49, 39, 25, 29, 28, 17, 2, 14, 10, 47, 7, 24, 11, 21, 45, 34, 6, 33}

Returns: 218
{10, 34, 43, 29, 17, 0, 37, 44, 41, 6, 32, 22, 9, 47, 38, 11, 40, 16, 35, 18, 28, 21, 2, 26, 25, 23, 49, 3, 31, 24, 46, 7, 27, 4, 48, 14, 8, 19, 33, 30, 5, 12, 42, 39, 13, 15, 20, 45, 1, 36}

Returns: 244
{33, 4, 40, 34, 6, 9, 5, 18, 23, 31, 10, 20, 45, 3, 2, 13, 26, 47, 11, 32, 46, 22, 37, 12, 42, 27, 36, 44, 25, 48, 21, 17, 43, 0, 49, 1, 30, 24, 19, 28, 41, 8, 15, 38, 16, 29, 39, 14, 35, 7}

Returns: 222
{31, 18, 33, 24, 32, 48, 42, 8, 40, 23, 2, 27, 38, 9, 43, 17, 39, 12, 28, 49, 10, 19, 36, 34, 22, 1, 35, 44, 5, 37, 29, 4, 46, 26, 7, 25, 6, 41, 13, 14, 45, 0, 3, 21, 15, 30, 11, 47, 16, 20}

Returns: 220
{31, 37, 42, 11, 7, 29, 45, 25, 15, 10, 2, 16, 1, 0, 9, 43, 3, 12, 19, 38, 44, 36, 17, 32, 5, 23, 14, 34, 35, 20, 22, 41, 21, 13, 18, 40, 26, 46, 48, 47, 49, 8, 6, 27, 30, 24, 4, 28, 39, 33}

Returns: 224
{34, 49, 23, 1, 26, 40, 16, 38, 39, 0, 9, 31, 29, 42, 7, 18, 8, 41, 32, 13, 19, 46, 3, 17, 14, 48, 43, 45, 30, 33, 2, 6, 36, 44, 28, 20, 24, 22, 47, 12, 37, 35, 10, 15, 27, 5, 11, 4, 21, 25}

Returns: 220
{23, 42, 4, 40, 20, 14, 49, 48, 8, 27, 5, 21, 26, 32, 12, 29, 10, 2, 6, 25, 39, 7, 37, 17, 24, 13, 35, 16, 38, 11, 0, 44, 31, 15, 46, 30, 19, 18, 47, 9, 36, 34, 28, 43, 1, 22, 33, 3, 45, 41}

Returns: 220
{28, 30, 37, 42, 33, 8, 4, 1, 43, 45, 3, 7, 16, 29, 48, 13, 35, 20, 39, 24, 17, 2, 34, 23, 44, 49, 25, 9, 46, 47, 38, 32, 5, 19, 0, 18, 36, 21, 15, 22, 27, 26, 12, 11, 40, 10, 14, 41, 6, 31}

Returns: 218
{9, 1, 13, 12, 48, 42, 44, 31, 18, 29, 6, 47, 21, 28, 32, 11, 22, 0, 35, 41, 5, 25, 17, 3, 10, 2, 8, 20, 7, 39, 49, 46, 16, 14, 33, 23, 26, 37, 30, 45, 27, 43, 36, 15, 4, 34, 38, 40, 24, 19}

Returns: 222
{49, 21, 5, 22, 24, 28, 2, 25, 48, 16, 23, 40, 45, 10, 12, 33, 38, 32, 17, 4, 37, 43, 29, 11, 46, 1, 8, 20, 47, 27, 13, 9, 36, 30, 39, 35, 3, 31, 26, 7, 19, 0, 44, 34, 18, 42, 6, 14, 41, 15}

Returns: 216
{18, 20, 30, 33, 40, 31, 38, 10, 17, 21, 19, 4, 13, 25, 49, 43, 6, 39, 24, 26, 36, 9, 35, 48, 46, 47, 45, 41, 27, 8, 22, 15, 29, 2, 34, 32, 3, 16, 23, 1, 12, 0, 14, 37, 7, 5, 28, 44, 11, 42}

Returns: 216
{12, 31, 15, 39, 2, 24, 22, 33, 34, 4, 49, 25, 20, 26, 18, 38, 13, 43, 40, 17, 19, 44, 36, 9, 28, 10, 23, 14, 11, 5, 21, 32, 45, 7, 42, 30, 3, 35, 29, 48, 0, 41, 47, 27, 6, 8, 37, 16, 1, 46}

Returns: 216
{32, 47, 13, 19, 37, 16, 29, 20, 8, 15, 40, 46, 25, 43, 5, 39, 12, 41, 7, 44, 30, 38, 34, 6, 42, 3, 36, 28, 23, 10, 4, 49, 9, 22, 0, 48, 17, 24, 1, 14, 31, 2, 18, 26, 35, 11, 33, 21, 27, 45}

Returns: 230
{12, 3, 48, 5, 2, 7, 6, 15, 0, 31, 40, 42, 33, 49, 47, 19, 26, 11, 21, 17, 24, 4, 43, 30, 39, 16, 38, 46, 28, 10, 37, 27, 35, 45, 25, 29, 36, 41, 32, 1, 44, 23, 22, 9, 34, 8, 18, 20, 13, 14}

Returns: 224
{46, 43, 24, 19, 26, 20, 37, 21, 33, 40, 2, 10, 4, 29, 45, 14, 41, 34, 35, 9, 5, 44, 12, 7, 22, 30, 31, 18, 47, 6, 8, 11, 28, 36, 0, 48, 15, 1, 38, 42, 39, 32, 23, 27, 16, 13, 17, 25, 3, 49}

Returns: 224
{26, 2, 46, 37, 15, 0, 29, 3, 38, 18, 32, 11, 39, 41, 27, 4, 16, 33, 12, 6, 45, 48, 43, 20, 7, 47, 24, 35, 13, 34, 14, 28, 9, 8, 31, 5, 44, 40, 17, 42, 22, 21, 19, 10, 36, 23, 25, 49, 30, 1}

Returns: 232
{17, 6, 4, 11, 21, 13, 22, 23, 7, 19, 3, 15, 10, 18, 5, 9, 24, 8, 0, 12, 14, 20, 1, 2, 16}

Returns: 108
{4, 22, 0, 17, 20, 3, 10, 8, 16, 7, 13, 19, 21, 2, 18, 12, 14, 15, 11, 5, 6, 1, 9}

Returns: 100
{16, 33, 35, 15, 20, 41, 0, 6, 32, 12, 1, 2, 34, 24, 37, 22, 38, 30, 23, 40, 19, 17, 36, 13, 39, 11, 42, 28, 7, 5, 18, 25, 10, 4, 8, 27, 21, 14, 31, 9, 3, 26, 29}

Returns: 196
{0}

Returns: 2
{12, 14, 10, 3, 5, 9, 25, 21, 7, 0, 6, 27, 20, 17, 26, 13, 11, 1, 18, 8, 16, 22, 19, 2, 4, 23, 15, 24}

Returns: 134
{8, 25, 23, 10, 27, 19, 39, 1, 33, 38, 29, 11, 20, 7, 14, 13, 16, 21, 4, 36, 40, 32, 28, 15, 22, 24, 6, 26, 35, 18, 30, 12, 9, 37, 0, 2, 5, 31, 3, 17, 34}

Returns: 188
{21, 12, 23, 33, 16, 1, 8, 24, 29, 25, 5, 31, 28, 27, 19, 20, 10, 4, 0, 11, 18, 13, 7, 17, 30, 14, 6, 3, 32, 34, 22, 26, 2, 15, 9}

Returns: 152
{20, 12, 7, 11, 10, 1, 9, 15, 6, 4, 0, 14, 17, 8, 18, 2, 19, 3, 5, 16, 13, 21}

Returns: 108
{12, 11, 3, 6, 7, 4, 5, 0, 8, 10, 1, 9, 13, 2}

Returns: 62
{16, 19, 20, 9, 12, 6, 1, 2, 5, 4, 0, 18, 3, 11, 7, 8, 10, 21, 13, 22, 17, 15, 14}

Returns: 122
{10, 26, 22, 19, 17, 14, 0, 25, 3, 24, 23, 6, 2, 11, 15, 13, 20, 7, 9, 12, 8, 1, 21, 4, 27, 5, 18, 16}

Returns: 128
{15, 13, 7, 6, 9, 18, 14, 20, 16, 0, 11, 2, 4, 21, 10, 3, 22, 5, 8, 25, 17, 19, 24, 12, 23, 1}

Returns: 122
{17, 12, 14, 13, 4, 18, 11, 2, 6, 7, 8, 21, 1, 5, 22, 3, 16, 0, 10, 19, 20, 24, 15, 23, 9}

Returns: 110
{4, 23, 29, 28, 6, 21, 9, 1, 13, 11, 7, 22, 19, 24, 3, 27, 30, 17, 0, 15, 12, 16, 18, 32, 2, 14, 8, 25, 5, 26, 31, 20, 10}

Returns: 148
{32, 10, 12, 27, 38, 9, 36, 26, 11, 15, 21, 33, 18, 22, 30, 29, 13, 34, 4, 16, 28, 23, 2, 7, 14, 39, 6, 1, 25, 5, 40, 17, 0, 37, 41, 8, 31, 19, 20, 35, 3, 24}

Returns: 184
{0, 27, 18, 3, 14, 10, 22, 13, 9, 17, 15, 23, 12, 25, 7, 6, 21, 11, 24, 5, 4, 8, 2, 16, 1, 20, 19, 26}

Returns: 126
{11, 29, 25, 10, 15, 28, 8, 6, 0, 27, 1, 22, 24, 12, 4, 19, 26, 20, 13, 21, 14, 7, 17, 5, 16, 18, 3, 2, 9, 23}

Returns: 136
{14, 20, 19, 7, 11, 13, 21, 12, 5, 4, 2, 15, 8, 1, 0, 17, 16, 9, 3, 10, 6, 18}

Returns: 96
{7, 3, 15, 22, 23, 14, 8, 16, 0, 12, 20, 11, 19, 13, 1, 6, 4, 10, 21, 18, 5, 17, 9, 2}

Returns: 102
{2, 7, 10, 3, 12, 9, 4, 8, 11, 5, 6, 1, 0}

Returns: 56
{15, 18, 5, 14, 12, 4, 13, 3, 7, 10, 22, 16, 8, 20, 0, 2, 6, 17, 21, 1, 19, 9, 11}

Returns: 100
{9, 30, 3, 33, 28, 38, 48, 43, 39, 15, 1, 24, 45, 40, 13, 37, 49, 4, 29, 16, 7, 42, 41, 6, 47, 17, 14, 34, 23, 27, 5, 8, 0, 44, 12, 18, 46, 21, 36, 11, 22, 35, 31, 26, 20, 2, 19, 32, 10, 25}

Returns: 216
{0, 2, 1, 11, 3, 10, 7, 12, 4, 9, 13, 6, 8, 5}

Returns: 68
{15, 10, 5, 12, 6, 18, 17, 0, 11, 4, 1, 9, 23, 13, 2, 16, 8, 20, 19, 24, 22, 14, 21, 25, 3, 7}

Returns: 120
{0, 17, 15, 10, 5, 11, 28, 19, 26, 6, 4, 20, 13, 25, 21, 29, 16, 2, 12, 24, 30, 7, 27, 18, 3, 14, 1, 23, 9, 8, 22}

Returns: 136
{0, 1, 2}

Returns: 12
{0}

Returns: 2
{44, 24, 6, 27, 3, 1, 35, 33, 7, 28, 15, 8, 48, 42, 17, 26, 39, 30, 41, 23, 0, 4, 47, 25, 16, 2, 14, 20, 34, 37, 11, 9, 10, 21, 43, 45, 36, 46, 31, 13, 40, 32, 12, 5, 19, 18, 22, 38, 29}

Returns: 226
{7, 3, 0, 5, 2, 1, 6, 4}

Returns: 32
{0}

Returns: 2
{14, 6, 17, 16, 12, 5, 9, 8, 4, 10, 13, 11, 3, 1, 19, 15, 2, 7, 0, 20, 18}

Returns: 90
{0, 1, 2}

Returns: 12
{27, 43, 34, 33, 20, 26, 16, 19, 22, 21, 29, 36, 8, 4, 13, 41, 11, 12, 30, 25, 17, 15, 18, 42, 39, 28, 9, 0, 24, 1, 31, 6, 35, 7, 23, 5, 10, 40, 2, 32, 37, 38, 3, 14}

Returns: 196
{20, 2, 27, 14, 38, 33, 36, 25, 43, 41, 16, 3, 18, 9, 26, 5, 7, 19, 32, 29, 42, 12, 21, 15, 31, 8, 28, 22, 39, 0, 23, 4, 11, 37, 30, 40, 35, 1, 24, 13, 17, 34, 10, 6}

Returns: 192
{5, 15, 20, 25, 6, 4, 22, 16, 24, 2, 17, 23, 13, 10, 11, 8, 3, 12, 14, 18, 21, 0, 19, 7, 1, 9}

Returns: 114
{14, 6, 9, 10, 3, 5, 13, 2, 0, 12, 11, 1, 7, 4, 8}

Returns: 64
{18, 10, 17, 29, 24, 34, 30, 33, 38, 11, 6, 22, 27, 0, 5, 3, 35, 26, 12, 9, 23, 25, 4, 7, 15, 28, 1, 13, 20, 2, 32, 37, 16, 21, 19, 14, 8, 31, 36}

Returns: 180
{5, 6, 8, 3, 7, 2, 1, 4, 0, 9}

Returns: 42
{30, 13, 25, 12, 3, 40, 24, 36, 15, 19, 16, 33, 5, 34, 6, 27, 28, 44, 9, 11, 26, 42, 14, 32, 45, 2, 38, 18, 37, 31, 23, 22, 21, 1, 17, 20, 35, 8, 41, 0, 29, 7, 43, 39, 10, 4}

Returns: 200
{0, 14, 7, 1, 6, 21, 5, 16, 13, 8, 11, 9, 2, 18, 12, 10, 15, 19, 3, 4, 17, 20}

Returns: 120
{6, 1, 12, 5, 8, 0, 7, 3, 10, 11, 4, 9, 2}

Returns: 56
{15, 18, 16, 14, 12, 10, 3, 9, 0, 17, 1, 6, 19, 11, 2, 7, 4, 8, 5, 13}

Returns: 98
{4, 11, 7, 2, 9, 6, 13, 15, 14, 5, 10, 12, 1, 3, 0, 8}

Returns: 68
{15, 22, 12, 7, 31, 30, 3, 4, 16, 14, 23, 20, 11, 32, 5, 0, 1, 27, 29, 33, 28, 8, 21, 6, 18, 34, 19, 17, 2, 25, 9, 26, 24, 13, 10}

Returns: 156
{19, 2, 8, 12, 4, 14, 10, 13, 15, 17, 3, 0, 1, 6, 7, 5, 9, 20, 18, 16, 11}

Returns: 98
{11, 29, 33, 5, 10, 35, 4, 22, 18, 8, 37, 32, 19, 2, 12, 30, 15, 28, 1, 3, 36, 31, 9, 13, 16, 7, 24, 26, 6, 25, 23, 27, 21, 20, 0, 17, 34, 14}

Returns: 164
{5, 1, 4, 3, 2, 0, 9, 7, 8, 6}

Returns: 42
{6, 17, 11, 16, 21, 4, 19, 23, 13, 2, 9, 20, 5, 10, 7, 3, 15, 1, 12, 18, 0, 22, 14, 8}

Returns: 102
{26, 29, 30, 2, 14, 24, 6, 15, 31, 21, 8, 10, 22, 7, 18, 19, 9, 23, 16, 17, 13, 3, 11, 20, 5, 32, 0, 1, 12, 27, 25, 28, 4}

Returns: 146
{16, 6, 12, 19, 10, 7, 8, 14, 22, 21, 17, 15, 23, 5, 0, 11, 13, 25, 18, 24, 2, 3, 1, 9, 20, 4}

Returns: 112
{8, 26, 25, 28, 9, 5, 18, 0, 32, 3, 10, 27, 30, 33, 15, 7, 29, 11, 1, 12, 34, 31, 24, 19, 21, 36, 38, 6, 20, 16, 23, 2, 4, 14, 39, 17, 22, 13, 35, 37}

Returns: 196
{19, 5, 1, 14, 15, 12, 21, 10, 18, 9, 17, 4, 13, 8, 11, 2, 16, 0, 6, 7, 20, 3}

Returns: 94
{7, 3, 5, 11, 17, 22, 4, 13, 1, 25, 23, 18, 19, 12, 14, 24, 2, 6, 16, 0, 21, 20, 8, 15, 10, 9}

Returns: 114
{5, 7, 0, 4, 14, 2, 10, 8, 1, 12, 3, 6, 9, 13, 11, 15}

Returns: 92
{0, 3, 1, 2}

Returns: 16
{12, 2, 1, 3, 8, 9, 5, 4, 0, 6, 10, 11, 7}

Returns: 60
{0, 1, 2, 3}

Returns: 20
{0, 1, 2, 3}

Returns: 20
{12, 2, 4, 6, 5, 15, 16, 18, 9, 13, 10, 14, 11, 1, 0, 8, 17, 7, 3}

Returns: 84
{12, 13, 7, 23, 14, 21, 0, 22, 17, 11, 16, 1, 28, 4, 18, 9, 6, 25, 26, 10, 5, 27, 2, 19, 15, 8, 30, 29, 20, 3, 24}

Returns: 142
{7, 5, 19, 2, 16, 1, 18, 4, 15, 14, 12, 9, 20, 6, 10, 21, 0, 11, 8, 13, 3, 17}

Returns: 98
{6, 2, 5, 4, 0, 9, 3, 7, 8, 1}

Returns: 42
{0, 4, 2, 5, 3, 1}

Returns: 24
{5, 3, 1, 7, 6, 0, 2, 8, 10, 9, 4}

Returns: 46
{40, 14, 43, 20, 36, 32, 16, 30, 6, 10, 29, 27, 42, 44, 48, 37, 1, 39, 25, 12, 5, 8, 11, 26, 0, 17, 24, 7, 28, 49, 3, 22, 38, 21, 46, 33, 13, 9, 18, 35, 47, 19, 34, 41, 2, 31, 15, 4, 45, 23}

Returns: 218
{35, 28, 8, 41, 24, 42, 0, 47, 32, 25, 19, 37, 17, 36, 4, 39, 12, 46, 10, 34, 40, 44, 3, 30, 27, 6, 1, 49, 33, 11, 21, 14, 38, 2, 5, 29, 18, 9, 23, 31, 45, 16, 20, 15, 7, 26, 13, 22, 48, 43}

Returns: 244
{8, 37, 24, 25, 17, 23, 32, 19, 36, 0, 26, 31, 11, 30, 33, 6, 35, 22, 16, 34, 7, 12, 18, 28, 15, 21, 4, 38, 13, 2, 27, 5, 14, 29, 1, 20, 9, 39, 3, 10}

Returns: 174
{36, 26, 31, 5, 6, 9, 3, 15, 19, 29, 22, 35, 8, 25, 33, 1, 37, 28, 16, 10, 17, 32, 18, 20, 4, 11, 34, 30, 21, 12, 14, 0, 7, 13, 23, 2, 24, 27}

Returns: 174
{3, 1, 0, 4, 2, 5}

Returns: 24
{45, 2, 1, 17, 22, 14, 33, 30, 27, 28, 38, 37, 10, 39, 5, 35, 13, 24, 11, 16, 29, 7, 41, 26, 34, 8, 9, 23, 15, 21, 42, 20, 40, 25, 18, 32, 44, 3, 12, 0, 4, 6, 19, 43, 31, 36}

Returns: 210
{2, 10, 12, 6, 4, 1, 5, 3, 11, 7, 8, 9, 13, 0}

Returns: 68
{19, 6, 25, 7, 27, 16, 31, 18, 21, 22, 9, 26, 3, 23, 12, 0, 29, 10, 28, 20, 5, 30, 1, 17, 13, 4, 14, 24, 11, 8, 15, 2}

Returns: 142
{2, 5, 3, 0, 6, 1, 4}

Returns: 28
{11, 1, 20, 0, 4, 37, 16, 8, 9, 24, 25, 33, 28, 15, 14, 7, 5, 34, 22, 10, 26, 3, 30, 12, 29, 19, 18, 2, 27, 35, 6, 32, 36, 31, 23, 17, 13, 21}

Returns: 172
{38, 9, 11, 18, 4, 5, 13, 17, 3, 7, 6, 12, 20, 27, 34, 0, 29, 30, 28, 10, 8, 22, 36, 37, 31, 21, 32, 23, 14, 26, 35, 33, 15, 16, 2, 19, 25, 1, 24}

Returns: 176
{0, 1, 2}

Returns: 12
{0, 34, 38, 1, 22, 3, 6, 15, 12, 39, 24, 11, 46, 33, 28, 4, 32, 42, 43, 18, 29, 7, 20, 23, 16, 17, 41, 40, 10, 31, 27, 2, 9, 36, 19, 45, 25, 26, 8, 37, 21, 44, 35, 14, 13, 5, 30}

Returns: 214
{32, 16, 0, 3, 33, 6, 7, 24, 28, 26, 30, 18, 14, 29, 8, 25, 20, 34, 15, 10, 12, 5, 4, 13, 39, 21, 23, 2, 11, 17, 36, 37, 31, 27, 38, 9, 35, 22, 1, 19}

Returns: 182
{10, 4, 1, 2, 3, 8, 7, 9, 11, 0, 6, 5}

Returns: 54
{0, 7, 1, 5, 6, 2, 3, 9, 8, 4}

Returns: 50
{2, 9, 8, 3, 1, 0, 5, 4, 6, 7 }

Returns: 46

Statistics

Problem Statement for "TreeSorter"

Problem Statement

Definition

Notes

Constraints

Examples