{"problem":{"name":"K. Cubes Shuffling","description":{"content":"It’s Friday, and unfortunately the curfew starts at 7 pm today. *Bakkar* and *Maymona* are very bored as they won’t be able to go out today. They decided to stay at home and try to do anything interes","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10028K"},"statements":[{"statement_type":"Markdown","content":"It’s Friday, and unfortunately the curfew starts at 7 pm today. *Bakkar* and *Maymona* are very bored as they won’t be able to go out today. They decided to stay at home and try to do anything interesting to entertain themselves. They searched in their old toys boxes for puzzles or games they could play, interestingly they found some cubes that are numbered with random numbers. They started to shuffle the cubes boringly in a random way to see what numbers they can make.\n\n*Maymona* then had an interesting idea, after shuffling the cubes in a row form, he started to sum up the sub-ranges of the cubes. for example if *Maymona* & *Bakkar* has 3 cubes numbered (1, 2, 3) they can then form 6 sub-ranges which are { [1], [2], [3], [1,2], [2,3], [1,2,3] }. Summing these sub-ranges { 1, 2, 3, 3, 5, 6 } we get a total sum of 20.\n\n*Maymona* called this game *‘Cubes Shuffling’* but *Bakkar* was not completely satisfied so he decided to make the game more interesting. He told *Maymona* they will take turns in shuffling the cubes and the first one who makes the shuffle with the minimum total sum of the sub-ranges would then be the winner. \n\n*Maymona* & *Bakkar* started playing; and after many turns of randomly shuffling the cubes, Bakkar noticed that he can get the minimum shuffle in just one turn.\n\nAs you are a friend of *Maymona* you would like to help *Maymona* know the secret behind {Bakkar’s} idea so you decided to write a program that given the cubes you would produce the arrangement that yields the minimum total sum of the sub-ranges. If multiple arrangements with the minimum total sum exists; you would produces the lexicographical smallest arrangement. An arrangement A is lexicographically smaller than an arrangement B with the same length if the first position they differ in is i and Ai < Bi.\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  1000). Followed by *T* test cases, each test case will consist of 2 lines. The first will contain a single integer *N*, the number of cubes available in the toys boxes (1  ≤  *N*  ≤  100). The second line will contain *N* integers, representing the values written on the cubes (1  ≤  values  ≤  109).\n\nFor each test case print a two lines. The first line contains \"Case n:\" (without the quotes) where n is the test case number (starting from 1). The second line will consist of the values in the minimum arrangement that can be produced, space separated.\n\n## Input\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  1000). Followed by *T* test cases, each test case will consist of 2 lines. The first will contain a single integer *N*, the number of cubes available in the toys boxes (1  ≤  *N*  ≤  100). The second line will contain *N* integers, representing the values written on the cubes (1  ≤  values  ≤  109).\n\n## Output\n\nFor each test case print a two lines. The first line contains \"Case n:\" (without the quotes) where n is the test case number (starting from 1). The second line will consist of the values in the minimum arrangement that can be produced, space separated.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of cubes.  \n- Let $ A_k = (a_{k,1}, a_{k,2}, \\dots, a_{k,n_k}) $ be a multiset of positive integers representing the cube values.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. For each $ k $:  \n   - $ 1 \\le n_k \\le 100 $  \n   - $ 1 \\le a_{k,i} \\le 10^9 $ for all $ i \\in \\{1, \\dots, n_k\\} $  \n\n**Objective**  \nFor each test case $ k $, find a permutation $ P_k = (p_1, p_2, \\dots, p_{n_k}) $ of $ A_k $ that minimizes the total sum of all contiguous subarray sums:  \n$$\nS(P_k) = \\sum_{i=1}^{n_k} \\sum_{j=i}^{n_k} \\sum_{\\ell=i}^{j} p_\\ell\n$$  \nIf multiple permutations achieve the minimum $ S(P_k) $, choose the lexicographically smallest one.  \n\n**Key Insight**  \nThe total sum over all contiguous subarrays of a permutation $ P = (p_1, \\dots, p_n) $ is:  \n$$\nS(P) = \\sum_{i=1}^n p_i \\cdot i \\cdot (n - i + 1)\n$$  \nThus, to minimize $ S(P) $, assign the smallest values to positions with the largest coefficients $ i(n - i + 1) $, and the largest values to positions with the smallest coefficients.  \nThe coefficient $ c_i = i(n - i + 1) $ is symmetric and maximized at the center. Hence, to minimize the total, sort the array in **ascending order** and place the smallest element at the position with the **largest coefficient** (i.e., center), next smallest at the next largest coefficient, etc. — this is equivalent to **sorting the array in ascending order** and placing it in the order of **decreasing coefficients**.  \n\nBut since $ c_i = i(n - i + 1) $ is symmetric and unimodal, the positions with largest coefficients are the **middle** ones. To get the **lexicographically smallest** arrangement among all minimizing permutations, we must assign the **smallest available number** to the **leftmost position** among those with maximum coefficient weight — but this requires a more precise strategy.\n\nActually, the minimal total sum is achieved when the sequence is sorted in **ascending order** — because the coefficient function $ c_i = i(n - i + 1) $ is convex, and by the rearrangement inequality, to minimize the weighted sum, we pair smallest elements with largest weights. But the largest weights are in the center. So we should place the **smallest elements in the center**? But then lexicographic order would be violated.\n\nWait — the correct known result:  \n> The total sum of all subarray sums is minimized when the array is sorted in **ascending order**.  \n> And this is also the lexicographically smallest arrangement achieving the minimum.\n\n**Why?**  \nBecause the total sum $ S(P) = \\sum_{i=1}^n p_i \\cdot c_i $, where $ c_i = i(n - i + 1) $.  \nThe weights $ c_i $ are fixed per position. The minimal total is achieved when the smallest $ p_i $ is multiplied by the largest $ c_i $, etc. — by rearrangement inequality. So we sort the values in ascending order, and sort the positions by descending weight, and assign accordingly.\n\nBut the weights $ c_i $ are symmetric:  \nFor $ n = 4 $: $ c = [4, 6, 6, 4] $  \nFor $ n = 5 $: $ c = [5, 8, 9, 8, 5] $  \n\nSo the center has highest weight. To minimize the total, assign smallest value to center, then next smallest to the next highest weights (positions 2 and 4), then largest to ends.\n\nBut then the arrangement is not sorted ascending — it’s \"valley-shaped\".\n\nHowever, the problem requires the **lexicographically smallest** arrangement among those achieving the minimum total.\n\nSo we must compute the assignment that minimizes the weighted sum and is lexicographically smallest.\n\nBut known from competitive programming:  \n> The minimal total sum of all subarray sums is achieved when the array is sorted in **ascending order**.  \n> And it is also the lexicographically smallest such arrangement.\n\nWait — let’s test with $ n=3 $, values [1,2,3]:  \n- Ascending: [1,2,3] → weights [3,4,3] → total = 1×3 + 2×4 + 3×3 = 3+8+9=20  \n- Try [2,1,3]: weights [3,4,3] → 2×3 +1×4 +3×3 = 6+4+9=19 → smaller!  \nSo ascending is NOT optimal.\n\nSo correct strategy:  \nSort the values in ascending order: $ v_1 \\le v_2 \\le \\dots \\le v_n $  \nSort the weights $ c_i = i(n - i + 1) $ in descending order, and assign the smallest value to the largest weight, etc.\n\nThen, to get lexicographically smallest arrangement, if multiple assignments yield same total, we must choose the lexicographically smallest permutation.\n\nBut the assignment is uniquely determined by sorting values ascending and weights descending — but the positions of equal weights matter.\n\nFor example, if two positions have same weight, we can swap the values assigned to them without changing total. To get lexicographically smallest, assign the smaller value to the leftmost position among those with equal weight.\n\nSo algorithm:  \n1. Compute weights $ c_i = i \\cdot (n - i + 1) $ for $ i = 1 $ to $ n $  \n2. Sort the cube values in ascending order  \n3. Create list of (weight, index) pairs, sort by weight descending, and for equal weights, by index ascending (so leftmost gets priority for smaller value)  \n4. Assign sorted values to these positions in order  \n5. Output the resulting permutation  \n\nThis gives the minimal total sum and lexicographically smallest arrangement.\n\n**Formal Output**\n\n**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of cubes.  \n- Let $ A_k = \\{a_{k,1}, \\dots, a_{k,n_k}\\} \\subset \\mathbb{Z}^+ $ be the multiset of cube values.  \n- Define the weight function $ c_i = i \\cdot (n_k - i + 1) $ for position $ i \\in \\{1, \\dots, n_k\\} $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. For each $ k $:  \n   - $ 1 \\le n_k \\le 100 $  \n   - $ 1 \\le a_{k,i} \\le 10^9 $  \n\n**Objective**  \nFor each test case $ k $, find a permutation $ P_k = (p_1, \\dots, p_{n_k}) $ of $ A_k $ minimizing:  \n$$\nS(P_k) = \\sum_{i=1}^{n_k} p_i \\cdot c_i\n$$  \nAmong all such minimizing permutations, choose the lexicographically smallest one.  \n\n**Solution Method**  \n1. Sort $ A_k $ in ascending order: $ v_1 \\le v_2 \\le \\dots \\le v_{n_k} $  \n2. Create list $ W = [(c_i, i) \\mid i = 1, \\dots, n_k] $  \n3. Sort $ W $ by:  \n   - Primary: $ c_i $ descending  \n   - Secondary: $ i $ ascending (to favor leftmost position in case of tie)  \n4. Assign $ v_j $ to the position indexed by the $ j $-th element in sorted $ W $, for $ j = 1 $ to $ n_k $  \n5. Output the resulting permutation.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10028K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}