Circle Permutation

Description

Input

對於給定的 n 個圓，設計一個優先隊列式分支限界法，計算 n 個圓的最佳排列方案，使 其長度達到最小。

Output

由文件 input.txt 給出輸入數據。第一行有 1 個正整數 n (1≤n≤20)。接下來的 1 行有 n 個數，表示 n 個圓的半徑。

Sample

將計算出的最小圓排列的長度輸出到文件 output.txt。

輸入文件示例

input.txt

3 1 1 2

輸出文件示例

output.txt

7.65685

Analysis

Brute-Force Method (DFS/BFS)

對於輸入，題目給定 n個圓，要求給出 長度最小的圓的排列。

則不妨考慮一個 Brute-Force Method思路：

推導： 兩圓相切時圓心的水平距公式

對於 生成n個圓的所有排列來說，這是容易的。

現在我們考慮，如果確實給定了 某個特定的圓排列方案，我們應如何 計算出該方案的長度。

我們設 兩個圓的 半徑 分別為 和 ，設 兩個圓的圓心水平距離為

實際上，我們發現，該 公式對於 上述的所有情況都是適用的。

計算 各個圓的 圓心水平坐標

我們已知知道 所有圓的排列順序，但是由於 兩個圓之間可能存在遮蓋，所以 排列長度並 無法從 所有的圓的半徑之中直接得到。

即

所以，我們需要一些額外信息：各個圓的圓心水平坐標

對於計算 數組，我們知道 某個圓的圓心水平坐標肯定與 該圓左側的圓的圓心水平坐標 存在關系

n.b. 我們這裏說的是 該圓左側的圓，而不是 該圓左邊的那1個圓。

實際上，我們如果要計算 某個圓的圓心水平坐標，需要把 該圓左側的所有圓都做考慮。

設我們有 圓的排列

對 圓的數量 運用 歸納法：

當我們考慮 時，存在一些問題。

不妨假設，第2個圓是 無窮小的，以至於 我們可以忽略掉 第2個圓，在這個假設下，我們可以得到

同理，我們可以假設 某個圓左側的所有圓 (除第一個圓外)是 無窮小的，這樣我們就可以 忽略掉這些圓。

進而得到

這裏並不是說 某圓 必須要和 第一個圓 發生 相切，只是拿 第一個圓進行舉例。

實際上，我們可以假設 任何圓是 無窮小的，從而使得 我們想要的兩個圓 發生 相切

換句話說：某個圓有可能與 該圓左側的所有圓發生 相切。

而不僅僅是與 該圓左邊的那一個圓發生 相切

則可得

n.b. 由於我們的公式是 假設兩圓之間相切而計算出的 兩圓的圓心距。

實際上，我們得到的 centers[k] 是 兩個圓恰好發生相切時的 閾值。

如果 圓A和 圓B 之間存在 某個足夠大的圓C，使得： 當 圓B和 圓A 發生 相切時， 圓B和 圓C必定早已 重疊 （而題目不允許圓發生重疊）

我們通過 函數可以非常巧妙地避開這個情形。

若 在圓A和圓B之間確實存在 足夠大的圓C，則有：

此時，函數將會 選擇讓 圓B和圓C發生相切，而 放棄讓 圓B和圓A相切

由於我們的 centers[k]計算的是 兩圓相切時的閾值：所以如果 圓B 與 圓A 和 圓C 能 同時相切，

則說明 圓A和 圓B的 大小相同的圓

計算 圓的排列長度

在已知 各個圓的半徑 和 各個圓的圓心的水平坐標 後

易得

該方法通過求 最右邊的區間端點和 最左邊的區間端點來求得 圓的排列長度

n.b. 最右邊的區間端點並不一定是 最後一個圓所給出的。

原因很簡單，我們可以簡單地假設 最後一個圓是 無窮小的，

那麽此時 最右邊的區間端點就與 最後一個圓沒有關系了。

BFS with Priority (Branch-Bound)

Introduction to branch-bound

我們回顧一下，前面所講的 DFS 和 BFS 本質上均屬於 Brute-Force Method。

DFS 按照 深度優先 方式在 一條路徑上進行 不斷深入進行搜索。

BFS 按照 廣度優先 方式在 當前節點 上進行 拓展 生成所有的 子節點，然後 按順序地逐個搜索 子節點

這兩種 搜索方式 是 盲目的 (Blind) 進行 搜索 (Search)，對他們而言，並不考慮 某個節點 所具有的 性質，而是將 所有的節點 都認為是 對等的 (Symmetric)。

比如說，DFS會首先沿著 整顆搜索空間樹 的 最左側路徑 (The Leftmost Path)進行 搜索。但是，有可能在 這條路徑 上根本就不存在 任何的合法解。

當然，如果 非常幸運的話，DFS 可以很快地在 最左側路徑上找到一個 最優解，然後利用 剪枝 (Prune) 來 大量地裁剪掉 整顆搜索空間樹 的 其余部分。

此時，DFS 將表現地非常良好。

如果可以為 DFS 盡可能早地 找到一個 較優的合法解，則可以利用 剪枝來 大幅度地 加快搜索。

但是，在很多情況下，我們可能 甚至 連一個 合法解 都無法找到，這時 DFS只能 陷入更加盲目的搜索當中 。

同樣地，BFS也有類似的 困境。

現在，我們基於 BFS 的 特性：每次從 當前節點生成 下一個子節點進行搜索。

如果我們使用 優先隊列 (Priority Queue) 將 BFS 在 搜索過程中的 節點 (Node) 按照 某種估價策略 (Cost Function) 進行 優先級排序，且每次只取出 當前的優先隊列中 價值最小的節點 (Minimum-Cost Node) 作為 下一個進行搜索的節點。

根據 問題的 優化目標，如果問題是 最大化問題，則取的是 價值最大的節點 。

則，我們實際上已經實現了一種 基於節點的價值的BFS搜索方式：

與普通的 BFS的區別在於，我們通過 價值函數 (Cost Function) 為 每個節點 (Node) 進行 估價，給該節點設置 價值 (Cost)，然後將該節點加入到 優先隊列，且每次只從 優先隊列 中取出 當前優先隊列中的價值最小的節點。

根據 Branch-Bound的概念，節點類型被分為下面3種：

  • 活節點 (Live-Node)：已經被 產生但仍未被 訪問的節點。
  • 正被探索節點 (E-Node)：當前 正在被訪問的節點，也就是 正在被拓展的節點。
  • 死節點 (Dead-Node)：已經被生成但將來不可能訪問或拓展的節點

How to define the cost-function

由於題目的目的是 最小化目標值，所以我們定義 價值函數為 目標值的下界。

下界並不一定是 嚴格下界，可以是 比較寬松的下界。

但我們期望的是：界限 盡可能地 逼近最優解的目標值

假定對於 n個圓的 排列方案 ，

已經確定了 前k個圓的 排列：

則我們可以計算 前k個圓的總長度

則對於 剩下的圓 ，設

則可以給出一個 下界：

因此，整合兩個式子得到：

n.b. 不等式 需要扣除

因為對於 來說，每個圓的長度 = 該圓半徑的兩倍

即

但對於處於 接壤處 的 圓 和 圓 ，

我們 實際上 擁有的是左半個圓 和 右半個圓

也就是說，我們並沒有擁有 整個圓

即

n.b. 準確地說，我們實際上是用 圖中的紅色半圓 來 替代 (Substitute) 圖中的綠色半圓

綜上，我們得出了 評估任何給定節點的下界的 價值函數

通常說，可以將 當前節點的情況進行 極端化假設 來獲得 界限：比如說使用 和 函數來使得 某些值屬於 最好的情況 或者 最壞的情況

另外，還有一種策略是通過為 當前節點 運行一個 貪心算法 (Greedy Method) 來獲取 界限。

比如，通過為 0/1 Knapsack 的 節點 運行一個 Fraction Knapsack的 Greedy Method 可以獲得一個 非常接近當前節點的最優解的合法解。

使用 Greedy Method來獲得 Bound 需要滿足：

  • 貪心選擇策略足夠簡單，使得 貪心算法不至於過慢
  • 所獲得的 貪心解大部分情況下 比較接近 當前節點的最優解

但對於 圓排列問題，我們不容易找到一種 貪心選擇策略足夠簡單，且貪心解比較接近當前節點的最優解 的 貪心選擇算法。

比如說，下面2種 貪心選擇策略：

  • 按照 降序/升序 排列 剩下的圓
  • 按照 大圓 和 小圓 交替的方式排列 剩下的圓

這是我們直觀想得到的策略，但它們給出的 貪心解 可能會 非常偏離 當前節點的最優解 。

第一個策略：我們其實已經知道，它將包含很多非 最優的子結構。實際上，這是一個 非常糟糕 的 貪心選擇策略

第二個策略：這個 貪心選擇策略 可能會稍微好一些，但仍然有可能 非常偏離 當前節點的最優解。

而且，我們可能會想對該策略進行 改進，使之變得更加 貪婪 (More Greedy)，比如說 盡可能多地包含更多小圓。

但是，如果 引入更復雜的貪心選擇策略 同時也增加了 價值函數 的 復雜度，在整個 BFS搜索過程 上有可能 得不償失

Accelerate the search by pruning

對於某些 我們已知不可能從中獲得最優解的節點，可以直接將 該節點 進行 丟棄。

Not better than current solution
// define the ans as the infinity for min-imization problem
ans = infinity

// when we reach a leaf-node, try to update the ans
ans = min(ans, node.cost)

// when we are in a non-leaf node, check the cost before expanding it
if (node.cost < ans) {
	expand the node
}
Out of bound
// before we expand a node, check the bound (cost-function)
if (bound(node) < ans) {
	expand the node
}
Contains substructures that are not optimal

根據 題目性質，通過 觀察可以發現，最優解不應當包含的 子結構。 如對於本題：

  1. 最優解必定不包含 連續的3個半徑升序的圓
  2. 最優解必定不包含 連續的3個半徑降序的圓
        // the radius of circles are sorted in ascending order: Arrays.sort(circles);
        // prune: we ensure that the best solution won't contain 3 successive ascending circles or 3 successive descending circles.
        if (node.level >= 2) {
            if (node.plan[node.level] > node.plan[node.level - 1] && node.plan[node.level - 1] > node.plan[node.level - 2]) {
                return Double.MAX_VALUE;
            }
            if (node.plan[node.level] < node.plan[node.level - 1] && node.plan[node.level - 1] < node.plan[node.level - 2]) {
                return Double.MAX_VALUE;
            }
        }

通過 剪枝 掉 擁有非最優子結構的節點，我們實際上可以非常好地利用 解的局部特征，並且更有可能 盡早地進行剪枝。

Accelerate the search by priority

相比於 BFS 和 DFS 的 盲目的搜索 而言，分支界限法使用了 價值函數來計算出 某個節點的界限，而且 搜索性能 極大程度地取決於 價值函數 是否 足夠聰明 (Intellectual)。

如果 價值函數 是 絕對聰明的 (Absolutely Intellectual)，那麽它就好像可以 預知未來一樣，直接從 成千上萬條可能的路徑之中，挑選出 1條最優解的路徑。

而如果 價值函數 不夠聰明，那麽它可能會被 某些節點 所 誤導，為 這些節點給出 錯誤的估價，從而導致 額外的沒有必要的搜索，但 後續仍然有機會重回正軌 (Bring us closer to the optimal solution) （如果 最優解所在的路徑上的節點沒有被 錯誤地剪枝掉的話）。

但對於 DFS而言，它從 最左側路徑開始 深入 進行搜索 ，如果 最優解處於 最右側路徑上的話，則會做 大量無用的搜索。

下面例子給出了當 指數爆炸 時，毫無目標地進行盲目搜索的DFS/BFS 和 擁有價值函數的分支界限 的不同 性能表現。

Branch and Bound
-----------------------------------------------------
Current Case: CIRCLE15.in & CIRCLE15.out
Expected  Input: [12, 48, 31, 18, 25, 33, 35, 73, 75, 65, 78, 94, 48]
Expected Output: [1121.467]
Your     Output: [1121.467]
Time Cost: 22052.981400 ms (22052981400 ns)
Accepted.
-----------------------------------------------------

DFS
-----------------------------------------------------
Current Case: CIRCLE15.in & CIRCLE15.out
Expected  Input: [12, 48, 31, 18, 25, 33, 35, 73, 75, 65, 78, 94, 48]
Expected Output: [1121.467]
Your     Output: [1121.467]
Time Cost: 66771.506100 ms (66771506100 ns)
Accepted.
-----------------------------------------------------

BFS
-----------------------------------------------------
Current Case: CIRCLE15.in & CIRCLE15.out
Expected  Input: [12, 48, 31, 18, 25, 33, 35, 73, 75, 65, 78, 94, 48]
Expected Output: [1121.467]
Your     Output: [1121.467]
Time Cost: 179924.051700 ms (179924051700 ns)
Accepted.
-----------------------------------------------------

Solution

DFS

Diagram

graph TD;
root((root)) --#0,1--> 0_((2.000));
0_ --#1,2--> 0_1_((5.828));
0_1_ --#2,9--> 0_1_2_((21.314));
0_1_2_ --#3,5--> 0_1_2_3_((30.730));
0_1_ --#4,5--> 0_1_3_((15.153));
0_1_3_ --#5,9--> 0_1_3_2_((32.569));
0_1_3_ --#6,9--> 0_1_3_2_((32.569));
style 0_1_3_2_ fill: lightgray
0_ --#7,9--> 0_2_((18.000));
0_2_ --#8,2--> 0_2_1_((19.485));
0_2_1_ --#9,5--> 0_2_1_3_((28.810));
0_2_ --#10,5--> 0_2_3_((27.416));
0_2_3_ --#11,2--> 0_2_3_1_((30.741));
0_ --#12,5--> 0_3_((10.472));
0_3_ --#13,2--> 0_3_1_((13.797));
0_3_1_ --#14,9--> 0_3_1_2_((29.282));
0_3_1_ --#15,9--> 0_3_1_2_((29.282));
style 0_3_1_2_ fill: lightgray
0_3_ --#16,9--> 0_3_2_((27.889));
0_3_2_ --#17,2--> 0_3_2_1_((29.374));
0_3_2_ --#18,2--> 0_3_2_1_((29.374));
style 0_3_2_1_ fill: lightgray
root((root)) --#19,2--> 1_((4.000));
1_ --#20,1--> 1_0_((5.828));
1_0_ --#21,9--> 1_0_2_((19.828));
1_0_2_ --#22,5--> 1_0_2_3_((29.245));
1_0_2_ --#23,5--> 1_0_2_3_((29.245));
style 1_0_2_3_ fill: lightgray
1_0_ --#24,5--> 1_0_3_((14.301));
1_0_3_ --#25,9--> 1_0_3_2_((31.717));
1_0_3_ --#26,9--> 1_0_3_2_((31.717));
style 1_0_3_2_ fill: lightgray
1_ --#27,9--> 1_2_((19.485));
1_2_ --#28,1--> 1_2_0_((19.485));
1_2_0_ --#29,5--> 1_2_0_3_((28.902));
1_2_0_ --#30,5--> 1_2_0_3_((28.902));
style 1_2_0_3_ fill: lightgray
1_2_ --#31,5--> 1_2_3_((28.902));
1_2_ --#32,5--> 1_2_3_((28.902));
style 1_2_3_ fill: lightgray
1_ --#33,5--> 1_3_((13.325));
1_3_ --#34,1--> 1_3_0_((13.797));
1_3_0_ --#35,9--> 1_3_0_2_((30.741));
1_3_0_ --#36,9--> 1_3_0_2_((30.741));
style 1_3_0_2_ fill: lightgray
1_3_ --#37,9--> 1_3_2_((30.741));
1_3_ --#38,9--> 1_3_2_((30.741));
style 1_3_2_ fill: lightgray
root((root)) --#39,9--> 2_((18.000));
2_ --#40,1--> 2_0_((18.000));
2_0_ --#41,2--> 2_0_1_((19.828));
2_0_1_ --#42,5--> 2_0_1_3_((29.153));
2_0_1_ --#43,5--> 2_0_1_3_((29.153));
style 2_0_1_3_ fill: lightgray
2_0_ --#44,5--> 2_0_3_((27.416));
2_0_3_ --#45,2--> 2_0_3_1_((30.741));
2_0_3_ --#46,2--> 2_0_3_1_((30.741));
style 2_0_3_1_ fill: lightgray
2_ --#47,2--> 2_1_((19.485));
2_1_ --#48,1--> 2_1_0_((21.314));
2_1_0_ --#49,5--> 2_1_0_3_((29.786));
2_1_0_ --#50,5--> 2_1_0_3_((29.786));
style 2_1_0_3_ fill: lightgray
2_1_ --#51,5--> 2_1_3_((28.810));
2_1_ --#52,5--> 2_1_3_((28.810));
style 2_1_3_ fill: lightgray
2_ --#53,5--> 2_3_((27.416));
2_3_ --#54,1--> 2_3_0_((27.889));
2_3_0_ --#55,2--> 2_3_0_1_((31.717));
2_3_0_ --#56,2--> 2_3_0_1_((31.717));
style 2_3_0_1_ fill: lightgray
2_3_ --#57,2--> 2_3_1_((30.741));
2_3_ --#58,2--> 2_3_1_((30.741));
style 2_3_1_ fill: lightgray
root((root)) --#59,5--> 3_((10.000));
3_ --#60,1--> 3_0_((10.472));
3_0_ --#61,2--> 3_0_1_((14.301));
3_0_1_ --#62,9--> 3_0_1_2_((29.786));
3_0_1_ --#63,9--> 3_0_1_2_((29.786));
style 3_0_1_2_ fill: lightgray
3_0_ --#64,9--> 3_0_2_((27.416));
3_0_2_ --#65,2--> 3_0_2_1_((28.902));
3_0_2_ --#66,2--> 3_0_2_1_((28.902));
style 3_0_2_1_ fill: lightgray
3_ --#67,2--> 3_1_((13.325));
3_1_ --#68,1--> 3_1_0_((15.153));
3_1_0_ --#69,9--> 3_1_0_2_((29.153));
3_1_0_ --#70,9--> 3_1_0_2_((29.153));
style 3_1_0_2_ fill: lightgray
3_1_ --#71,9--> 3_1_2_((28.810));
3_1_ --#72,9--> 3_1_2_((28.810));
style 3_1_2_ fill: lightgray
3_ --#73,9--> 3_2_((27.416));
3_2_ --#74,1--> 3_2_0_((27.416));
3_2_0_ --#75,2--> 3_2_0_1_((29.245));
3_2_0_ --#76,2--> 3_2_0_1_((29.245));
style 3_2_0_1_ fill: lightgray
3_2_ --#77,2--> 3_2_1_((28.902));
3_2_ --#78,2--> 3_2_1_((28.902));
style 3_2_1_ fill: lightgray

Source

public class CirclePermutationSolver_DFS {

    static Judger judger = new Judger("/Cases/Lab7/CIRCLE PERMUTATION").redirectErrorToErrorFile().disablePrettyFormat();
    
    /*
    all the circles should TOUCH THE GROUND, therefore we can't put one circle over another
    
    if we have an infinite big circle, we can put ALL the other circles under the big circle !
    
    for total n circles: the FIRST circle and the LAST circle is special.
    THE OTHER circles should considerate both of them.
    
    we can divide a circle into 2 PARTs
    
    we assume that: the first circle is in (0, 0)
     */
    
    public static double calc_center(int[] circles, int[] plan, int plan_index) {
        // if we only have 1 circle, we assume that the first circle is in (0, 0)
        double center = 0;
    
        /* compare circles[plan[plan_index]] with ALL the previous circles */
        for (int i = 0; i < plan_index; i++) {
            double r1 = circles[plan[i]];
            double r2 = circles[plan[plan_index]];
            center = Math.max(center, centers[i] + 2 * Math.sqrt(r1 * r2));
        }
        return center;
    }
    
    public static double calc_length(int[] circles, int[] plan) {
        /* all circles */
        // the first circle
        double interval_left = 0;
        double interval_right = 0;
        // it's ok if we only have 1 circle. calcCenter() will return 0 if we only have 1 circle
        for (int i = 0; i < plan.length; i++) {
            double r = circles[plan[i]];
            // current circle & left circle
            double c = calc_center(circles, plan, i);
            interval_left = Math.min(interval_left, c - r);
            interval_right = Math.max(interval_right, c + r);
        }
        return interval_right - interval_left;
    }
    
    /* Global Variables */
    static int n;
    static int[] circles;
    static boolean[] used;
    static double[] centers;
    static int[] plan;
    static double ans;
    
    public static void search(int depth) {
    
        /* Base Case */
        if (depth >= n) {
            ans = Math.min(ans, calc_length(circles, plan));
            return;
        }
    
        /* Recursion Case */
        for (int i = 0; i < circles.length; i++) {
            /* lock */
            if (used[i]) continue;
            else used[i] = true;
    
            /* update */
            plan[depth] = i;
            centers[depth] = calc_center(circles, plan, depth);
    
            // pruning increases speed by about 2 to 10 times !
            // n.b. the LHS is not the new length ! it's JUST a condition for pruning
            // if you want to get the new length, you ought to call calcLength()
            if (centers[depth] + circles[plan[0]] + circles[plan[depth]] < ans) {
                search(depth + 1);
            }
    
            /* unlock */
            used[i] = false;
        }
    }
    
    public static void solve(Scanner scanner) {
    
        /* Initialize */
        n = scanner.nextInt();
        circles = new int[n];
        centers = new double[n];
        for (int i = 0; i < n; i++) {
            circles[i] = scanner.nextInt();
        }
        used = new boolean[n];
        plan = new int[n];
        ans = Double.MAX_VALUE;
    
        /* Algo */
        search(0);
        System.out.printf("%.3f", ans);
    }
    
    public static void main(String[] args) {
        for (Scanner scanner : judger) {
            solve(scanner);
        }
    }
}

Benchmark

-----------------------------------------------------
Current Case: CIRCLE0.in & CIRCLE0.out
Expected  Input: [3, 1 1 2]
Expected Output: [7.657]
Your     Output: [7.657]
Time Cost: 2.953300 ms (2953300 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE1.in & CIRCLE1.out
Expected  Input: [5, 59 23 41 70 47 ]
Expected Output: [454.388]
Your     Output: [454.388]
Time Cost: 1.378200 ms (1378200 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE10.in & CIRCLE10.out
Expected  Input: [10, 9 2 117 45 9 3 142 14 9 98 ]
Expected Output: [755.928]
Your     Output: [755.928]
Time Cost: 866.089000 ms (866089000 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE11.in & CIRCLE11.out
Expected  Input: [2, 10000 1]
Expected Output: [20000.000]
Your     Output: [20000.000]
Time Cost: 0.695200 ms (695200 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE12.in & CIRCLE12.out
Expected  Input: [2, 10000 10000]
Expected Output: [40000.000]
Your     Output: [40000.000]
Time Cost: 0.688300 ms (688300 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE13.in & CIRCLE13.out
Expected  Input: [1, 10000]
Expected Output: [20000.000]
Your     Output: [20000.000]
Time Cost: 0.700300 ms (700300 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE2.in & CIRCLE2.out
Expected  Input: [7, 94 35 20 88 55 28 57 ]
Expected Output: [666.874]
Your     Output: [666.874]
Time Cost: 1.431800 ms (1431800 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE3.in & CIRCLE3.out
Expected  Input: [7, 25 1 5 74 47 77 8 ]
Expected Output: [415.089]
Your     Output: [415.089]
Time Cost: 1.630000 ms (1630000 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE4.in & CIRCLE4.out
Expected  Input: [9, 17 49 77 84 86 64 75 88 65 ]
Expected Output: [1159.668]
Your     Output: [1159.668]
Time Cost: 44.285300 ms (44285300 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE5.in & CIRCLE5.out
Expected  Input: [10, 99 22 17 45 91 73 42 14 9 98 ]
Expected Output: [858.474]
Your     Output: [858.474]
Time Cost: 447.405000 ms (447405000 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE6.in & CIRCLE6.out
Expected  Input: [10, 51 100 66 37 30 83 87 98 31 43 ]
Expected Output: [1140.471]
Your     Output: [1140.471]
Time Cost: 409.175500 ms (409175500 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE7.in & CIRCLE7.out
Expected  Input: [10, 51 100 66 37 30 1 87 98 31 3 ]
Expected Output: [902.696]
Your     Output: [902.696]
Time Cost: 550.624100 ms (550624100 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE8.in & CIRCLE8.out
Expected  Input: [9, 1 49 77 8 86 6 75 88 3 ]
Expected Output: [738.394]
Your     Output: [738.394]
Time Cost: 83.854200 ms (83854200 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE9.in & CIRCLE9.out
Expected  Input: [10, 9 22 17 45 9 3 42 14 9 98 ]
Expected Output: [400.389]
Your     Output: [400.389]
Time Cost: 343.135900 ms (343135900 ns)
Accepted.
-----------------------------------------------------
Result Statistics: √ √ √ √ √ √ √ √ √ √ √ √ √ √

BFS

Diagram

graph TD;
root((root)) --#0,1--> 0_((2.000));
root((root)) --#1,1--> 1_((4.000));
root((root)) --#2,1--> 2_((18.000));
root((root)) --#3,1--> 3_((10.000));
3_ --#4,2--> 3_0_((10.472));
3_ --#5,2--> 3_1_((13.325));
3_ --#6,2--> 3_2_((27.416));
3_2_ --#7,9--> 3_2_0_((27.416));
3_2_ --#8,9--> 3_2_1_((28.902));
3_2_1_ --#9,5--> 3_2_1_0_((30.730));
3_2_0_ --#10,5--> 3_2_0_1_((29.245));
3_1_ --#11,9--> 3_1_0_((15.153));
3_1_ --#12,9--> 3_1_2_((28.810));
3_1_2_ --#13,5--> 3_1_2_0_((28.810));
3_1_0_ --#14,5--> 3_1_0_2_((29.153));
style 3_1_0_2_ fill: lightgray
3_0_ --#15,9--> 3_0_1_((14.301));
3_0_ --#16,9--> 3_0_2_((27.416));
3_0_2_ --#17,5--> 3_0_2_1_((28.902));
style 3_0_2_1_ fill: lightgray
3_0_1_ --#18,5--> 3_0_1_2_((29.786));
style 3_0_1_2_ fill: lightgray
2_ --#19,2--> 2_0_((18.000));
2_ --#20,2--> 2_1_((19.485));
2_ --#21,2--> 2_3_((27.416));
2_3_ --#22,9--> 2_3_0_((27.889));
2_3_ --#23,9--> 2_3_1_((30.741));
style 2_3_1_ fill: lightgray
2_3_0_ --#24,5--> 2_3_0_1_((31.717));
style 2_3_0_1_ fill: lightgray
2_1_ --#25,9--> 2_1_0_((21.314));
2_1_ --#26,9--> 2_1_3_((28.810));
style 2_1_3_ fill: lightgray
2_1_0_ --#27,5--> 2_1_0_3_((29.786));
style 2_1_0_3_ fill: lightgray
2_0_ --#28,9--> 2_0_1_((19.828));
2_0_ --#29,9--> 2_0_3_((27.416));
2_0_3_ --#30,5--> 2_0_3_1_((30.741));
style 2_0_3_1_ fill: lightgray
2_0_1_ --#31,5--> 2_0_1_3_((29.153));
style 2_0_1_3_ fill: lightgray
1_ --#32,2--> 1_0_((5.828));
1_ --#33,2--> 1_2_((19.485));
1_ --#34,2--> 1_3_((13.325));
1_3_ --#35,9--> 1_3_0_((13.797));
1_3_ --#36,9--> 1_3_2_((30.741));
style 1_3_2_ fill: lightgray
1_3_0_ --#37,5--> 1_3_0_2_((30.741));
style 1_3_0_2_ fill: lightgray
1_2_ --#38,9--> 1_2_0_((19.485));
1_2_ --#39,9--> 1_2_3_((28.902));
style 1_2_3_ fill: lightgray
1_2_0_ --#40,5--> 1_2_0_3_((28.902));
style 1_2_0_3_ fill: lightgray
1_0_ --#41,9--> 1_0_2_((19.828));
1_0_ --#42,9--> 1_0_3_((14.301));
1_0_3_ --#43,5--> 1_0_3_2_((31.717));
style 1_0_3_2_ fill: lightgray
1_0_2_ --#44,5--> 1_0_2_3_((29.245));
style 1_0_2_3_ fill: lightgray
0_ --#45,2--> 0_1_((5.828));
0_ --#46,2--> 0_2_((18.000));
0_ --#47,2--> 0_3_((10.472));
0_3_ --#48,9--> 0_3_1_((13.797));
0_3_ --#49,9--> 0_3_2_((27.889));
0_3_2_ --#50,5--> 0_3_2_1_((29.374));
style 0_3_2_1_ fill: lightgray
0_3_1_ --#51,5--> 0_3_1_2_((29.282));
style 0_3_1_2_ fill: lightgray
0_2_ --#52,9--> 0_2_1_((19.485));
0_2_ --#53,9--> 0_2_3_((27.416));
0_2_3_ --#54,5--> 0_2_3_1_((30.741));
style 0_2_3_1_ fill: lightgray
0_2_1_ --#55,5--> 0_2_1_3_((28.810));
style 0_2_1_3_ fill: lightgray
0_1_ --#56,9--> 0_1_2_((21.314));
0_1_ --#57,9--> 0_1_3_((15.153));
0_1_3_ --#58,5--> 0_1_3_2_((32.569));
style 0_1_3_2_ fill: lightgray
0_1_2_ --#59,5--> 0_1_2_3_((30.730));
style 0_1_2_3_ fill: lightgray

Source

public class CirclePermutationSolver_BFS {

    static Judger judger = new Judger("/Cases/Lab7/CIRCLE PERMUTATION").redirectErrorToErrorFile().disablePrettyFormat();
    
    /*
    all the circles should TOUCH THE GROUND, therefore we can't put one circle over another
    if we have an infinite big circle, we can put ALL the other circles under the big circle !
    
    for total n circles: the FIRST circle and the LAST circle is special.
    THE OTHER circles should considerate both of them.
    
    we can divide a circle into 2 PARTs
    
    ---
    take 2 circles into considerations:
    Case1: luckily, we have a big enough circle to cover another circle
    Case2: we can't cover the other circle, but we can cover the big circle
     */
    static class Node {
    
        /* State */
        public int level;
        public int[] plan;
        public double[] centers;
        // n.b. if we use swap() to generate circle permutation, we don't need the used field !
        public boolean[] used;
    
        public Node(int level, int[] plan, double[] centers, boolean[] used) {
            this.level = level;
            this.plan = plan;
            this.centers = centers;
            this.used = used;
        }
    }
    
    public static double calc_center(int[] circles, int[] plan, double[] centers, int level) {
        // if we only have 1 circle, we assume that the first circle is in (0, 0)
        double center = 0;
    
        /* compare circles[plan[plan_index]] with ALL the previous circles */
        for (int i = 0; i < level; i++) {
            double r1 = circles[plan[i]];
            double r2 = circles[plan[level]];
            center = Math.max(center, centers[i] + 2 * Math.sqrt(r1 * r2));
        }
        return center;
    }
    
    public static double calc_length(int[] circles, int[] plan, double[] centers, int level) {
        /* all circles */
        // the first circle
        double interval_left = 0;
        double interval_right = 0;
        // it's ok if we only have 1 circle. calcCenter() will return 0 if we only have 1 circle
        for (int i = 0; i <= level; i++) {
            double r = circles[plan[i]];
            // current circle & left circle
            double c = centers[i];
            interval_left = Math.min(interval_left, c - r);
            interval_right = Math.max(interval_right, c + r);
        }
    
        return interval_right - interval_left;
    }
    
    public static double ans;
    
    public static double solve(int n, int[] circles) {
    
        /* Initialize */
        ans = Double.MAX_VALUE;
    
        /* Construct the queue and init */
        LinkedList<Node> nodes = new LinkedList<>();
        nodes.add(new Node(-1, new int[n], new double[n], new boolean[n]));
    
        // BFS
        while (!nodes.isEmpty()) {
    
            // Get one node
            Node currentNode = nodes.poll();
            int $level = currentNode.level + 1;
    
            /* Generate all the next nodes */
            for (int k = 0; k < n; k++) {
                // Skip the used circles
                if (currentNode.used[k]) continue;
    
                // Generate the next node
                int[] $plan = currentNode.plan.clone();
                $plan[$level] = k;
    
                double[] $centers = currentNode.centers.clone();
                $centers[$level] = calc_center(circles, $plan, $centers, $level);
    
                boolean[] $used = currentNode.used.clone();
                $used[k] = true;
    
                /* Update the next node */
                double length = calc_length(circles, $plan, $centers, $level);
    
                // ADD of DROP the next node ?
                // prune: if the next-node is NOT BETTER THAN current solution
                if (length < ans) {
                    /* Try to update ans */
                    Node node = new Node($level, $plan, $centers, $used);
                    /* Finish permutation ! */
                    if ($level == n - 1) {
                        ans = Math.min(ans, length);
                    } else nodes.push(node);
                }
            }
        }
    
        return ans;
    }
    
    public static void main(String[] args) {
        for (Scanner scanner : judger) {
            int n = scanner.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            System.out.printf("%.3f", solve(n, a));
        }
    }
}

Benchmark

-----------------------------------------------------
Current Case: CIRCLE0.in & CIRCLE0.out
Expected  Input: [3, 1 1 2]
Expected Output: [7.657]
Your     Output: [7.657]
Time Cost: 3.026100 ms (3026100 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE1.in & CIRCLE1.out
Expected  Input: [5, 59 23 41 70 47 ]
Expected Output: [454.388]
Your     Output: [454.388]
Time Cost: 1.600400 ms (1600400 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE10.in & CIRCLE10.out
Expected  Input: [10, 9 2 117 45 9 3 142 14 9 98 ]
Expected Output: [755.928]
Your     Output: [755.928]
Time Cost: 2300.654100 ms (2300654100 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE11.in & CIRCLE11.out
Expected  Input: [2, 10000 1]
Expected Output: [20000.000]
Your     Output: [20000.000]
Time Cost: 0.799000 ms (799000 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE12.in & CIRCLE12.out
Expected  Input: [2, 10000 10000]
Expected Output: [40000.000]
Your     Output: [40000.000]
Time Cost: 0.685500 ms (685500 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE13.in & CIRCLE13.out
Expected  Input: [1, 10000]
Expected Output: [20000.000]
Your     Output: [20000.000]
Time Cost: 0.686900 ms (686900 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE2.in & CIRCLE2.out
Expected  Input: [7, 94 35 20 88 55 28 57 ]
Expected Output: [666.874]
Your     Output: [666.874]
Time Cost: 6.327000 ms (6327000 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE3.in & CIRCLE3.out
Expected  Input: [7, 25 1 5 74 47 77 8 ]
Expected Output: [415.089]
Your     Output: [415.089]
Time Cost: 5.280500 ms (5280500 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE4.in & CIRCLE4.out
Expected  Input: [9, 17 49 77 84 86 64 75 88 65 ]
Expected Output: [1159.668]
Your     Output: [1159.668]
Time Cost: 316.421300 ms (316421300 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE5.in & CIRCLE5.out
Expected  Input: [10, 99 22 17 45 91 73 42 14 9 98 ]
Expected Output: [858.474]
Your     Output: [858.474]
Time Cost: 3063.122800 ms (3063122800 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE6.in & CIRCLE6.out
Expected  Input: [10, 51 100 66 37 30 83 87 98 31 43 ]
Expected Output: [1140.471]
Your     Output: [1140.471]
Time Cost: 3877.059500 ms (3877059500 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE7.in & CIRCLE7.out
Expected  Input: [10, 51 100 66 37 30 1 87 98 31 3 ]
Expected Output: [902.696]
Your     Output: [902.696]
Time Cost: 3195.105900 ms (3195105900 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE8.in & CIRCLE8.out
Expected  Input: [9, 1 49 77 8 86 6 75 88 3 ]
Expected Output: [738.394]
Your     Output: [738.394]
Time Cost: 216.487600 ms (216487600 ns)
Accepted.
-----------------------------------------------------
Current Case: CIRCLE9.in & CIRCLE9.out
Expected  Input: [10, 9 22 17 45 9 3 42 14 9 98 ]
Expected Output: [400.389]
Your     Output: [400.389]
Time Cost: 2362.946400 ms (2362946400 ns)
Accepted.
-----------------------------------------------------
Result Statistics: √ √ √ √ √ √ √ √ √ √ √ √ √ √

 

Branch-Bound

Diagram

graph TD;
root((root)) --#0,1--> 0_((2.000</br>8.000));
root((root)) --#1,2--> 1_((4.000</br>9.000));
root((root)) --#2,5--> 2_((10.000</br>12.000));
root((root)) --#3,9--> 3_((18.000</br>16.000));
0_ --#4,2--> 0_1_((5.828</br>13.828));
0_ --#5,5--> 0_2_((10.472</br>15.472));
0_ --#6,9--> 0_3_((18.000</br>17.000));
1_ --#7,1--> 1_0_((5.828</br>9.828));
1_ --#8,5--> 1_2_((13.325</br>13.325));
1_ --#9,9--> 1_3_((19.485</br>15.485));
1_0_ --#10,5--> 1_0_2_((14.301</br>24.301));
1_0_ --#11,9--> 1_0_3_((19.828</br>25.828));
0_1_ --#12,5--> 0_1_2_((15.153</br>INF));
style 0_1_2_ fill: lightgray
0_1_ --#13,9--> 0_1_3_((21.314</br>INF));
style 0_1_3_ fill: lightgray
2_ --#14,2--> 2_1_((13.325</br>16.325));
2_ --#15,1--> 2_0_((10.472</br>14.472));
2_ --#16,9--> 2_3_((27.416</br>23.416));
1_2_ --#17,1--> 1_2_0_((13.797</br>15.797));
1_2_ --#18,9--> 1_2_3_((30.741</br>INF));
style 1_2_3_ fill: lightgray
2_0_ --#19,2--> 2_0_1_((14.301</br>18.301));
2_0_ --#20,9--> 2_0_3_((27.416</br>24.416));
0_2_ --#21,2--> 0_2_1_((13.797</br>17.797));
0_2_ --#22,9--> 0_2_3_((27.889</br>INF));
style 0_2_3_ fill: lightgray
1_2_0_ --#23,9--> 1_2_0_3_((30.741</br>30.741));
0_2_1_ --#24,9--> 0_2_1_3_((29.282</br>29.282));
2_0_1_ --#25,9--> 2_0_1_3_((29.786</br>INF));
style 2_0_1_3_ fill: lightgray
2_1_ --#26,1--> 2_1_0_((15.153</br>INF));
style 2_1_0_ fill: lightgray
2_1_ --#27,9--> 2_1_3_((28.810</br>22.810));
1_3_ --#28,5--> 1_3_2_((28.902</br>26.902));
1_3_ --#29,1--> 1_3_0_((19.485</br>19.485));
0_3_ --#30,5--> 0_3_2_((27.416</br>26.416));
0_3_ --#31,2--> 0_3_1_((19.485</br>21.485));
3_ --#32,2--> 3_1_((19.485</br>22.485));
3_ --#33,5--> 3_2_((27.416</br>27.416));
3_ --#34,1--> 3_0_((18.000</br>20.000));
1_3_0_ --#35,5--> 1_3_0_2_((28.902</br>28.902));
0_3_1_ --#36,5--> 0_3_1_2_((28.810</br>26.810));
3_0_ --#37,5--> 3_0_2_((27.416</br>28.416));
3_0_ --#38,2--> 3_0_1_((19.828</br>23.828));
3_1_ --#39,5--> 3_1_2_((28.810</br>26.810));
style 3_1_2_ fill: lightgray
3_1_ --#40,1--> 3_1_0_((21.314</br>INF));
style 3_1_0_ fill: lightgray
2_1_3_ --#41,1--> 2_1_3_0_((28.810</br>26.810));
3_0_1_ --#42,5--> 3_0_1_2_((29.153</br>INF));
style 3_0_1_2_ fill: lightgray
1_0_2_ --#43,9--> 1_0_2_3_((31.717</br>INF));
style 1_0_2_3_ fill: lightgray
2_3_ --#44,1--> 2_3_0_((27.416</br>27.416));
2_3_ --#45,2--> 2_3_1_((28.902</br>29.902));
style 2_3_1_ fill: lightgray
2_0_3_ --#46,2--> 2_0_3_1_((28.902</br>28.902));
style 2_0_3_1_ fill: lightgray
1_0_3_ --#47,5--> 1_0_3_2_((29.245</br>29.245));
style 1_0_3_2_ fill: lightgray
1_3_2_ --#48,1--> 1_3_2_0_((29.374</br>INF));
style 1_3_2_0_ fill: lightgray
0_3_2_ --#49,2--> 0_3_2_1_((30.741</br>INF));
style 0_3_2_1_ fill: lightgray
2_3_0_ --#50,2--> 2_3_0_1_((29.245</br>29.245));
style 2_3_0_1_ fill: lightgray
3_0_2_ --#51,2--> 3_0_2_1_((30.741</br>30.741));
style 3_0_2_1_ fill: lightgray
3_2_ --#52,2--> 3_2_1_((30.741</br>INF));
style 3_2_1_ fill: lightgray
3_2_ --#53,1--> 3_2_0_((27.889</br>INF));
style 3_2_0_ fill: lightgray

Source

public class CirclePermutationSolver_BranchBoundMethod {

    static Judger judger = new Judger("/Cases/Lab7/CIRCLE PERMUTATION").redirectErrorToErrorFile().disablePrettyFormat();
    
    static class Node {
    
        /* State */
        public int level;
        // n.b. we use swap() to generate permutation, so used[] is useless.
        public int[] plan;
        public double[] centers;
    
        /* Model */
        public double cost = 0;
        public static int n;
        public static int[] circles;
        public static double ans;
    
        public Node(int level, int[] plan, double[] centers) {
            this.level = level;
            this.plan = plan;
            this.centers = centers;
        }
    
        public String radius_string() {
            int[] radius = new int[this.level + 1];
            for (int i = 0; i <= this.level; i++) {
                radius[i] = Node.circles[this.plan[i]];
            }
            return Arrays.toString(radius);
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "level=" + level +
                    ", radius=" + radius_string() +
                    ", centers=" + Arrays.toString(centers) +
                    ", cost=" + cost +
                    '}';
        }
    }
    
    /*
    n.b. This function use centers[0..level - 1] to calculate centers[level].
    Therefore, centers[0..level - 1] should be initialized and computed before calling this function
     */
    public static double calc_center(int[] circles, int[] plan, double[] centers, int level) {
        // if we only have 1 circle, we assume that the first circle is in (0, 0)
        double center = 0;
    
        /* compare circles[plan[plan_index]] with ALL the previous circles */
        for (int k = 0; k < level; k++) {
            double r1 = circles[plan[k]];
            double r2 = circles[plan[level]];
            center = Math.max(center, centers[k] + 2 * Math.sqrt(r1 * r2));
        }
        return center;
    }
    
    /* This function only does some easy things: for all the circles, use its center and radius to calc (c+r) and (c-r).
     *  and then use min(c-r) and max(c+r) to calculate the interval length.
     *  n.b. centers[0..level] should be initialized and computed before calling this function
     * */
    public static double calc_length(int[] circles, int[] plan, double[] centers, int level) {
        /* all circles */
        // the first circle
        double interval_left = 0;
        double interval_right = 0;
        // it's ok if we only have 1 circle. calcCenter() will return 0 if we only have 1 circle
        for (int i = 0; i <= level; i++) {
            double r = circles[plan[i]];
            double c = centers[i];
            interval_left = Math.min(interval_left, c - r);
            interval_right = Math.max(interval_right, c + r);
        }
    
        return interval_right - interval_left;
    }
    
    public static double calc_cost(Node node) {
        // the radius of circles are sorted in ascending order: Arrays.sort(circles);
        // prune: we ensure that the best solution won't contain 3 successive ascending circles or 3 successive descending circles.
        if (node.level >= 2) {
            if (node.plan[node.level] > node.plan[node.level - 1] && node.plan[node.level - 1] > node.plan[node.level - 2]) {
                return Double.MAX_VALUE;
            }
            if (node.plan[node.level] < node.plan[node.level - 1] && node.plan[node.level - 1] < node.plan[node.level - 2]) {
                return Double.MAX_VALUE;
            }
        }
    
        double cost = 0;
        double x_k = node.centers[node.level];
        // n.b. r_1 ... r_k totally k circles
        double r_1 = Node.circles[node.plan[0]];
        cost += x_k;
        cost += r_1;
        // n.b. we drop the r_k: cost += r_k;
        // since the radius of r is the min-imum radius of the circles[k+1..n], we can know r <= r_k ,
        // it's safe for us to assume lower-bound of the length of circles[k+1..n] is (left_circles_amount * (2 * r))
        double r_k = Node.circles[node.plan[node.level]];
        double r = r_k;
        for (int i = node.level + 1; i < Node.n; i++) {
            r = Math.min(r, Node.circles[node.plan[i]]);
        }
        cost += (2 * (Node.n - node.level - 1) + 1) * r;
        return cost;
    }
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static double solve(int n, int[] circles) {
    
        /* Initialize */
        // n.b. in ascending order of circle radius
        Arrays.sort(circles);
        Node.n = n;
        Node.circles = circles;
        Node.ans = Double.MAX_VALUE;
    
        /* Construct the queue and init */
        PriorityQueue<Node> PQ = new PriorityQueue<>((o1, o2) -> {
            // n.b. if o1.cost == o2.cost, we need to compare o1.level and o2.level
            // it's also ok if you considerate the LEVEL inside your COST function.
            // we have tried and found that: more complex comparator won't benefit us more.
            return (int) ((o1.cost - o1.level) - (o2.cost - o2.level));
        });
    
        // add dummy node
        int[] root_node = new int[n];
        for (int i = 0; i < n; i++) root_node[i] = i;
        PQ.add(new Node(-1, root_node, new double[n]));
    
        // BFS with Priority
        while (!PQ.isEmpty()) {
    
            /* Get one node */
            Node current_node = PQ.poll();
            int $level = current_node.level + 1;
    
            /* Generate all the next nodes */
            for (int k = $level; k < n; k++) {
    
                /* Generate the next-node */
                int[] $plan = current_node.plan.clone();
                swap($plan, $level, k);
    
                double[] $centers = current_node.centers.clone();
                $centers[$level] = calc_center(circles, $plan, $centers, $level);
    
                /* Check the node ! */
                // n.b. centers[level] + circles[plan[0]] + circles[plan[level]] is NOT ALWAYS the LENGTH of the plan !
                // prune: if the next-node is NOT BETTER THAN current solution, skip it
                if ($centers[$level] + circles[$plan[0]] + circles[$plan[$level]] < Node.ans) {
    
                    Node $ = new Node($level, $plan, $centers);
                    $.cost = calc_cost($);
    
                    // prune:  if the next-node is out of BOUND
                    if ($.cost < Node.ans) {
                        if ($level == n - 1) {
                            Node.ans = Math.min(Node.ans, calc_length(circles, $plan, $centers, $level));
                        } else PQ.add($);
                    }
                }
            }
        }
        return Node.ans;
    }
    
    public static void main(String[] args) {
        for (Scanner scanner : judger) {
            int n = scanner.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            System.out.printf("%.3f", solve(n, a));
        }
    }
}

Benchmark

-----------------------------------------------------
Current Case: CIRCLE0.in & CIRCLE0.out
Expected  Input: [3, 1 1 2]
Expected Output: [7.657]
Your     Output: [7.657]
Time Cost: 4.585800 ms (4585800 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE1.in & CIRCLE1.out
Expected  Input: [5, 59 23 41 70 47 ]
Expected Output: [454.388]
Your     Output: [454.388]
Time Cost: 1.767200 ms (1767200 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE10.in & CIRCLE10.out
Expected  Input: [10, 9 2 117 45 9 3 142 14 9 98 ]
Expected Output: [755.928]
Your     Output: [755.928]
Time Cost: 235.701100 ms (235701100 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE11.in & CIRCLE11.out
Expected  Input: [2, 10000 1]
Expected Output: [20000.000]
Your     Output: [20000.000]
Time Cost: 1.475400 ms (1475400 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE12.in & CIRCLE12.out
Expected  Input: [2, 10000 10000]
Expected Output: [40000.000]
Your     Output: [40000.000]
Time Cost: 1.274300 ms (1274300 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE13.in & CIRCLE13.out
Expected  Input: [6, 1 1 2 2 3 5]
Expected Output: [24.136]
Your     Output: [24.136]
Time Cost: 1.613500 ms (1613500 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE14.in & CIRCLE14.out
Expected  Input: [3, 1 2 9]
Expected Output: [19.485]
Your     Output: [19.485]
Time Cost: 1.742700 ms (1742700 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE2.in & CIRCLE2.out
Expected  Input: [7, 94 35 20 88 55 28 57 ]
Expected Output: [666.874]
Your     Output: [666.874]
Time Cost: 2.466700 ms (2466700 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE3.in & CIRCLE3.out
Expected  Input: [7, 25 1 5 74 47 77 8 ]
Expected Output: [415.089]
Your     Output: [415.089]
Time Cost: 3.496700 ms (3496700 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE4.in & CIRCLE4.out
Expected  Input: [9, 17 49 77 84 86 64 75 88 65 ]
Expected Output: [1159.668]
Your     Output: [1159.668]
Time Cost: 49.480700 ms (49480700 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE5.in & CIRCLE5.out
Expected  Input: [10, 99 22 17 45 91 73 42 14 9 98 ]
Expected Output: [858.474]
Your     Output: [858.474]
Time Cost: 176.674800 ms (176674800 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE6.in & CIRCLE6.out
Expected  Input: [10, 51 100 66 37 30 83 87 98 31 43 ]
Expected Output: [1140.471]
Your     Output: [1140.471]
Time Cost: 193.609000 ms (193609000 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE7.in & CIRCLE7.out
Expected  Input: [10, 51 100 66 37 30 1 87 98 31 3 ]
Expected Output: [902.696]
Your     Output: [902.696]
Time Cost: 179.229300 ms (179229300 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE8.in & CIRCLE8.out
Expected  Input: [9, 1 49 77 8 86 6 75 88 3 ]
Expected Output: [738.394]
Your     Output: [738.394]
Time Cost: 21.907700 ms (21907700 ns)
Accepted
-----------------------------------------------------
Current Case: CIRCLE9.in & CIRCLE9.out
Expected  Input: [10, 9 22 17 45 9 3 42 14 9 98 ]
Expected Output: [400.389]
Your     Output: [400.389]
Time Cost: 120.563100 ms (120563100 ns)
Accepted
-----------------------------------------------------
Result Statistics: √ √ √ √ √ √ √ √ √ √ √ √ √ √ √

Reference

  1. Coursera, Design and Analysis of Algorithms - Circle Permutation
  2. CSDN, myy_cjw, 圓排列問題
  3. CSDN, Lrish Coffee, 圓排列問題