Nasser's Parity Array Transformation#12356

Nasser's Parity Array Transformation (Editorial)

Problem Author:	Mohammad Nasser (MOAGEZA)
Prepared by:	Mohammad Nasser (MOAGEZA)
Edited by:	Hasan Saleh (MathModel)

Solution

General Idea: We can only increase elements by $1$ using operations on same-parity subarrays. If any element $a_{i} > x$ a_i > x, it's impossible since we can only increase values.

Key Observation:

When we increment an element, we can pair it with a neighbor to minimize total operations. The strategy is to greedily process elements from smallest to largest.

Algorithm:

Sort elements by value while tracking their original positions.
For each element (starting from smallest):
- Look at its left and right neighbors in the original array.
- Choose the neighbor with smaller value (costs less to increment together).
- Add the difference: $(neighbor value - current value)$ (\text{neighbor value} - \text{current value}) to the answer.
- Remove the current element from consideration.
Finally, add $(x - max (a))$ (x - \max(a)) to bring the maximum element to $x$ .

The minimum number of operations is:

i = 0 \sum n - 2 (min (left neighbor, right neighbor) - a_{i}) + (x - max (a))

\sum_{i=0}^{n-2} (\min(\text{left neighbor}, \text{right neighbor}) - a_i) + (x - \max(a))

The solution runs in $O (n lo g n)$ \mathcal{O}(n \log n) time per test case due to sorting and set operations.

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n, x, mx = 0, ans = 0;
    cin >> n >> x;
    vector<int> a(n);
    set<int> s;
    vector<pair<int, int>> v;
    
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
        s.insert(i);
        v.push_back({a[i], i});
    }
    
    if(mx > x){
        cout << -1;
        return;
    }
    
    sort(v.begin(), v.end());
    
    for(int i = 0; i < n - 1; i++){
        int val = v[i].first, idx = v[i].second;
        int res1 = 2e9, res2 = 2e9;
        s.erase(idx);
        
        auto it = s.upper_bound(idx);
        if(it != s.end()){
            res1 = a[*it];
        }
        if(it != s.begin()){
            it--;
            res2 = a[*it];
        }
        
        ans += min(res1, res2) - val;
    }
    
    ans += x - mx;
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while(t--){
        solve();
        cout << '\n';
    }
    return 0;
}