CF #636-D

 D. Constant Palindrome Sum

Problem Statement: here

Solution:

This question requires prior knowledge of computing prefix sum technique. This allows us to solve the question in O(N)

So, for every pair (a[i],a[n-i-1]) -> we will use map to count the number of pairs with sum exactly equal to x. we will mark the minimum possible sum and maximum possible sum with at most one change in value in the pref array. 

When we take the prefix sum of this array, we get the count of exactly how many pairs can have the sum as x, given they can change at most one element. Note that x can vary from 2 to 2*k. 

Since the total number of pairs are N/2, and we know that pref[sum] are the total number of elements with at most one changes, we can do N/2  - pref[sum] to get the number of pairs in which we need to do 2 changes to achieve that sum. Also, to this, we can add pref[i] - m[i] to get exactly those #pairs which requires one change to get the sum. 

Implementation:

ll pref[400005]; void solve() { clr(pref,0); ll n,k; cin>>n>>k; ll a[n]; rep(i,0,n) cin >> a[i]; mll m; rep(i,0,n/2){ ll sum = a[i] + a[n-i-1]; m[sum]++; pref[min(a[i],a[n-i-1])+1]++; pref[max(a[i],a[n-i-1])+k+1]--; } rep(i,2,2*k+1) pref[i] = pref[i-1] + pref[i]; ll ans=inf; rep(i,2,2*k+1){ ans = min(ans,2*(n/2-pref[i]) + pref[i]-m[i]); } cout << ans << endl; }