Balanced
Contest: Codeforces Round 983 (Div. 2)
Difficulty rating: 2400
Tags: constructive algorithms, data structures, greedy, implementation, math

You are given a cyclic array $$$a$$$ with $$$n$$$ elements, where $$$n$$$ is odd. In each operation, you can do the following:

- Choose an index $$$1 \le i \le n$$$ and increase $$$a_{i - 1}$$$ by $$$1$$$, $$$a_i$$$ by $$$2$$$, and $$$a_{i + 1}$$$ by $$$1$$$. The element before the first element is the last element because this is a cyclic array.

A cyclic array is called balanced if all its elements are equal to each other.

Find any sequence of operations to make this cyclic array balanced or determine that it is impossible. Please note that you do not have to minimize the number of operations.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n < 2 \cdot 10^5$$$, $$$n$$$ is odd) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{6}$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case:

- If it is impossible to make the cyclic array balanced, output $$$-1$$$.
- Otherwise, output $$$n$$$ integers $$$v_1, v_2, \ldots, v_n$$$ ($$$0 \leq v_i \leq 10^{18}$$$) — where $$$v_i$$$ denotes the number of operations applied to index $$$i$$$. It can be proved that if any solution exists, then there exists a solution under the given constraints. If there are several solutions under the given constraints, output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

- After $$$1$$$ operation applied to index $$$i = 2$$$, the array $$$a = [3, 3, 3]$$$.

In the second test case:

- After $$$2$$$ operations applied to index $$$i = 1$$$, the array $$$a = [5, 4, 5]$$$.
- After $$$1$$$ operation applied to index $$$i = 2$$$, the array $$$a = [6, 6, 6]$$$.

In the third test case:

- After $$$2$$$ operations applied to index $$$i = 1$$$, the array $$$a = [5, 4, 1, 2, 3]$$$.
- After $$$3$$$ operations applied to index $$$i = 3$$$, the array $$$a = [5, 7, 7, 5, 3]$$$.
- After $$$2$$$ operations applied to index $$$i = 5$$$, the array $$$a = [7, 7, 7, 7, 7]$$$.

Example input:
6
3
2 1 2
3
1 2 3
5
1 2 1 2 1
7
1 2 1 2 1 3 1
9
10000 10000 10000 10000 10000 10001 10002 10001 10000
1
10

Example output:
0 1 0 
2 1 0 
2 0 3 0 2 
4 2 7 0 8 0 6 
1 1 1 1 1 1 0 1 1 
0

Editorial:
To simplify this problem a little bit before starting, we will temporarily allow "negative" operation: choose an index $$$1 \le i \le n$$$ and increase $$$a_{i - 1}$$$ by $$$-1$$$, $$$a_i$$$ by $$$-2$$$, and $$$a_{i + 1}$$$ by $$$-1$$$. This is counted as $$$-1$$$ operation on index $$$i$$$. Should we get negative elements in array $$$v$$$ in the end, we can normalize it just fine by subtracting all $$$v_i$$$ with $$$\min v_i$$$ so that the final array $$$v$$$ is valid — it's trivial to prove that applying the same amount of operations in all indices does not change the relative difference between any two values in the array.
Imagine we have $$$n = 3$$$ and array $$$a = [a_1, a_2, a_3]$$$ where $$$a_1 \ge a_2 \le a_3$$$; i.e., a trench. This array always has at least one solution: try to balance $$$a_1$$$ and $$$a_3$$$ by adding an amount of operation on either side based on their difference — here we have something we'll denote as a "balanced trench", then add another amount of operations on index $$$2$$$ to balance them three, and due to the cyclic nature of $$$a$$$.
In fact, every array with $$$n = 3$$$, without regards to value intensity, can be thought of this form — if $$$a_2$$$ is higher than both $$$a_1$$$ and $$$a_3$$$, the act of "raising" $$$a_2$$$ is actually applying a negative amount of operations to index $$$2$$$.
How to make a "balanced trench" for $$$n > 3$$$?
At least, we can balance $$$a_1$$$ and $$$a_n$$$ in the same fashion as we did for $$$n = 3$$$. Can we balance $$$a_2$$$ and $$$a_{n-1}$$$ without breaking the balance we achieved between $$$a_1$$$ and $$$a_n$$$?
Assuming we have an array $$$[0, x, y, x + 1, 0]$$$.
By logic, we want to increase the value of index $$$2$$$.
Applying an operation to index $$$1$$$ won't do, as the new array would be $$$[2, x+1, y, x+1, 1]$$$. We are balancing the inner elements by sacrificing the outer ones.
Applying an operation to index $$$3$$$ also won't do as it increases both sides.
Applying an operation to index $$$2$$$ will make the array become $$$[1, x+2, y+1, x+1, 0]$$$. By applying another operation to index $$$5$$$, we'll reach our desired goal with array $$$[2, x+2, y+1, x+2, 2]$$$.
In fact, a series of operations in "consecutive" indices of the same parity would have this effect, regardless of how long that series is.
To be precise, without loss of generality, a series of operations in indices $$$2, 4, \ldots, i$$$, with $$$i \le n-1$$$, will increase $$$a_1$$$ and $$$a_{i+1}$$$ by $$$1$$$, and all values with indices in range $$$[2, i]$$$ by $$$2$$$.
The catch here is that we mitigate $$$1$$$ unit of difference between sides with each operation series by adding just $$$1$$$ unit to the higher side, while the corresponding other $$$1$$$ would be further beyond the lower side.
If we aim to balance the sides from outwards to inwards, that exceeding $$$1$$$ will either fall into a deeper-inwards layer, or the center of the array (since $$$n$$$ is odd), which will not harm whatever we have achieved at first.
Take an example with array $$$[48, 18, 26, 57, 39]$$$.
• First, we'll balance index $$$1$$$ and index $$$5$$$. We can simply apply $$$9$$$ operations to index $$$5$$$. The new array would be $$$[57, 18, 26, 66, 57]$$$.
• Then, we'll balance index $$$2$$$ and index $$$4$$$. From index $$$2$$$, we'll move to the left until it reaches index $$$5$$$, and apply $$$48$$$ operations for every $$$2$$$ steps. In other words, apply $$$48$$$ operations to index $$$2$$$ and $$$48$$$ operations to index $$$5$$$. This array is now a balanced trench: $$$[153, 114, 64, 114, 153]$$$.
Now, achieving the desired array (we'll call it a "plateau") from a balanced trench is easy: starting from the rightmost element of the left side before the center going leftwards, compare the value to its adjacent element to the right, and apply a corresponding amount of operations.
Now, take the balanced trench we just acquired.
• First, we'll check index $$$2$$$. Clearly, we want to rise index $$$3$$$ to close the $$$50$$$ unit gap, thus we'll apply $$$50$$$ operations to index $$$3$$$. The new array will become $$$[153, 164, 164, 164, 153]$$$.
• Then, we'll check index $$$1$$$. Our objective is to decrease $$$11$$$ for all elements with indices in range $$$[2, 4]$$$. Using the similar operation series as discussed earlier, this can be done like this: apply $$$-11$$$ operations to index $$$2$$$, then apply $$$-11$$$ operations to index $$$4$$$. The final array will be $$$[142, 142, 142, 142, 142]$$$.
• That operation series can be used here because the range of elements changing by $$$2$$$ units per series has an odd size, and since we're growing the plateau from the center point outwards, its size is always odd as well.
With this, the non-normalized array $$$v$$$ will be $$$[0, 46, 50, -11, 57]$$$.
Implementing this method can be separated into two separate steps:
• Step $$$1$$$ (creating the balanced trench): for each pair of indices $$$(i, n+1-i)$$$ with difference $$$a_{n+1-i} - a_i = d$$$, apply $$$d$$$ operations for each index of the cyclic range $$$[n+3-i, i]$$$ with step $$$2$$$.
• Step $$$2$$$ (creating the plateau): for each pair of indices $$$(i, i+1)$$$ with difference $$$a_i - a_{i+1} = d$$$, apply $$$d$$$ operations for each index of the range $$$[i+1, n-i]$$$ with step $$$2$$$.
Some extra notes:
• Each step requires an independent prefix-sum structure to quickly maintain the operation updates. Notice that the prefix sum here takes account of parity, since only the other index in a range is updated, not every one of them.
• Remember that after each index considered, its value will alter based on the amount of operations just applied on it, so keep track of it properly.
• To avoid confusion, it's advised to apply the operations of step $$$1$$$ directly into array $$$a$$$ before proceeding with step $$$2$$$.
• Remember to normalize array $$$v$$$ before outputting to get rid of negative values.
• Refer to the model solution for more details.
Time complexity: $$$\mathcal{O}(n)$$$.