## Intuition The problem requires us to make all elements of an array equal using a series of operations. Each operation allows us to transfer a positive integer value from one element to another. The key insight is that if we can balance the array such that all elements have the same value, we can achieve the desired outcome. The challenge is to determine if this is possible and, if so, how to perform the operations efficiently. ## Approach 1. **Check Feasibility**: - Calculate the total sum of the array elements. - If the sum is not divisible by `n`, it's impossible to make all elements equal, and we should output `-1`. 2. **Target Value**: - If feasible, the target value for each element is the total sum divided by `n`. 3. **Balancing the Array**: - Iterate over the array and for each element, calculate how much it needs to give or receive to reach the target value. - Use a series of operations to adjust the elements: - If an element `a[i]` is greater than the target, it can give the excess to other elements. - If an element `a[i]` is less than the target, it needs to receive the deficit from other elements. - We can perform operations in a way that ensures no more than `3n` operations are needed. 4. **Implementation Details**: - Use a greedy approach to transfer excess from elements that are above the target to those below it. - Keep track of operations and ensure all elements reach the target value. ## Complexity - **Time Complexity**: `O(n)` per test case, as we iterate over the array and perform a constant amount of work for each element. - **Space Complexity**: `O(n)` for storing operations. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; vector a(n); long long sum = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; sum += a[i]; } if (sum % n != 0) { cout << -1 << '\n'; continue; } long long target = sum / n; vector> operations; for (int i = 1; i < n; ++i) { if (a[i] % (i + 1) != 0) { int need = (i + 1) - (a[i] % (i + 1)); operations.emplace_back(1, i + 1, need); a[0] -= need; a[i] += need; } int give = a[i] / (i + 1); operations.emplace_back(i + 1, 1, give); a[0] += give * (i + 1); a[i] -= give * (i + 1); } for (int i = 1; i < n; ++i) { operations.emplace_back(1, i + 1, target); } cout << operations.size() << '\n'; for (auto &[i, j, x] : operations) { cout << i << ' ' << j << ' ' << x << '\n'; } } return 0; } ``` This solution efficiently balances the array by redistributing values using a series of operations, ensuring all elements become equal to the target value. The operations are constructed such that they do not exceed the allowed `3n` operations.

Make Them Equal

Problem Details