CF 1783A - Make it Beautiful
We are given an array of integers sorted in non-decreasing order, and we need to rearrange its elements so that no element equals the sum of all previous elements. If such a rearrangement is impossible, we must report it.
Rating: 800
Tags: constructive algorithms, math, sortings
Solve time: 1m 43s
Verified: no
Solution
Problem Understanding
We are given an array of integers sorted in non-decreasing order, and we need to rearrange its elements so that no element equals the sum of all previous elements. If such a rearrangement is impossible, we must report it. The input consists of multiple test cases, each with the array length and its elements. The output is either "NO" or "YES" followed by a beautiful arrangement.
The constraints are small: the array length $n$ is at most 50, and element values are between 1 and 100. With $t \le 2000$, even a $O(n^2)$ solution would run efficiently, since $n^2 \cdot t \le 5 \cdot 10^6$ operations.
A key edge case occurs when all elements are equal, especially for $n = 2$, because the second element will always equal the sum of all previous elements. For example, with $a = [10, 10]$, any permutation will have the second element equal to the first, making it impossible to be beautiful. Another edge case is when the sum of the smaller elements equals the largest element, which can occur in arrays like $[1, 2, 3]$ if sorted naively. Careless implementations that simply leave the array sorted risk creating ugly arrays.
Approaches
The brute-force approach would be to try every permutation of the array and check if it is beautiful. Checking an array of length $n$ takes $O(n)$, but there are $n!$ permutations. For $n = 50$, this is infeasible, even with our small input limit, because $50!$ is astronomically large.
The key observation is that only the largest element can potentially match the sum of all previous elements in a sorted array. If we place the largest element last and the rest of the elements before it, the sum of all earlier elements is maximized, making it most likely to equal the largest element. To avoid this, we can place the largest element first, ensuring no prior sum can match it, or we can sort the array in non-increasing order. Sorting in descending order guarantees that the sum of all elements before any position is strictly larger than the current element, except possibly for arrays with all elements equal. If all elements are equal and $n > 1$, then the second element will always equal the sum of previous elements only if $n = 2$ and the value is repeated. This gives a simple and safe rearrangement strategy: sort descending, check the first two elements. If they are equal and the array has only two elements, print NO; otherwise, print the rearranged array.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(n! · n) | O(n) | Too slow |
| Descending Sort | O(n log n) | O(n) | Accepted |
Algorithm Walkthrough
- Read the number of test cases $t$.
- For each test case, read $n$ and the array $a$.
- Sort the array $a$ in descending order. This ensures that each element is not equal to the sum of all elements before it because sums increase as we move to the right.
- Check if $n = 2$ and the two elements are equal. If so, print NO. This handles the special impossible case where the second element always equals the first.
- Otherwise, print YES followed by the sorted array. This guarantees a beautiful array because the sum of any prefix cannot equal the current element when the array is sorted descending.
Why it works: By placing larger elements first, any prefix sum is always smaller than the next element, except in the trivial impossible case. Descending order eliminates the risk of any element being equal to the sum of elements before it, and the only exception (two equal numbers) is explicitly handled.
Python Solution
import sys
input = sys.stdin.readline
def make_beautiful():
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
if n == 2 and a[0] == a[1]:
print("NO")
else:
print("YES")
print(" ".join(map(str, a)))
if __name__ == "__main__":
make_beautiful()
The code first reads the number of test cases. Each array is sorted in descending order to prevent ugly configurations. The special case of two equal numbers is handled explicitly. Printing the array as a string ensures the output format matches the problem requirements. Sorting in place reduces memory overhead.
Worked Examples
Example 1
Input array: [3, 3, 6, 6]
Sorted descending: [6, 6, 3, 3]
| Step | Prefix Sum | Current Element | Ugly? |
|---|---|---|---|
| 1 | 0 | 6 | No |
| 2 | 6 | 6 | No |
| 3 | 12 | 3 | No |
| 4 | 15 | 3 | No |
All elements pass, output: YES 6 6 3 3.
Example 2
Input array: [10, 10]
Sorted descending: [10, 10]
| Step | Prefix Sum | Current Element | Ugly? |
|---|---|---|---|
| 1 | 0 | 10 | No |
| 2 | 10 | 10 | Yes |
Output: NO. This shows the special two-equal case.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) per test case | Sorting dominates, n ≤ 50 |
| Space | O(n) | Storing the array |
The total operations over all test cases is at most $2000 * 50 \log 50$, which is well within the 3-second limit. Memory usage is small, comfortably under 512 MB.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
from contextlib import redirect_stdout
out = io.StringIO()
with redirect_stdout(out):
make_beautiful()
return out.getvalue().strip()
# provided samples
assert run("4\n4\n3 3 6 6\n2\n10 10\n5\n1 2 3 4 5\n3\n1 4 4\n") == \
"YES\n6 6 3 3\nNO\nYES\n5 4 3 2 1\nYES\n4 4 1", "sample 1"
# custom cases
assert run("1\n2\n1 2\n") == "YES\n2 1", "ascending small array"
assert run("1\n3\n5 5 5\n") == "YES\n5 5 5", "all equal, n>2"
assert run("1\n50\n" + " ".join(str(i) for i in range(1,51)) + "\n") == \
"YES\n" + " ".join(str(i) for i in range(50,0,-1)), "max size ascending"
assert run("1\n2\n100 100\n") == "NO", "two equal max values"
| Test input | Expected output | What it validates |
|---|---|---|
| 2 elements ascending | YES with descending | small array reordering |
| 3 equal elements | YES | all equal values, n>2 |
| 50 elements ascending | YES descending | maximum size input |
| 2 equal elements | NO | edge case impossible |
Edge Cases
The algorithm explicitly handles arrays with two equal elements, which are impossible to make beautiful. Arrays with more than two equal elements are safe because sorting descending avoids any prefix sum equality. Single-element arrays are not allowed by constraints. Arrays where the largest element equals the sum of smaller elements are automatically fixed by descending sort. For example, [1, 2, 3] becomes [3, 2, 1], avoiding the ugly sum in the middle. Each edge case is accounted for by sorting and the two-element check.