PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Prefix sums
PROBLEM:
You have an array A. The following operation can be performed:
- Choose an index i (1 \lt i \lt N) and an integer X.
- Subtract X from A_{i-1} and A_{i+1}, and add 2X to A_i.
Find the minimum number of moves needed to turn A into a palindrome.
EXPLANATION:
When working with operations like this, that affect a small number of indices close to each other, it’s often useful to look at prefix sums and/or difference arrays.
To that end, let P denote the prefix sum array of A; so that P_i = A_1 + A_2 + \ldots + A_N.
Note that the operation (i, X) on A changes P as follows:
- P_{i-1} decreases by X
- P_{i} increases by X.
- Everything else in unchanged.
This is, once again, an operation on an array dealing with adjacent elements.
Let’s look at prefix sums again!
Let Q_i = P_1 + P_2 + \ldots + P_i denote the prefix sum array of P.
The operation (i, X) on the original array now simply decreases Q_{i-1} by X, which seems relatively simple to deal with: after all, since X is allowed to be negative, “decrease Q_{i-1} by any value” really just means “set Q_{i-1} to any value”.
However, note that because of the nature of the operation, we cannot change Q_N and Q_{N-1} at all.
Now, suppose A is a palindrome, meaning A_i = A_{N+1-i} for every i. Let’s analyze what this means for Q.
Let’s also assume N is even for now, for convenience.
First off, note that Q_i can be written in terms of the elements of A as
When A is a palindrome, applying this to i = N tells us that
Q_N = (N+1) \cdot (A_1 + A_2 + \ldots + A_{N/2})
Recall that Q_N can’t be changed, so if it isn’t a multiple of (N+1), no solution exists.
It also fixes the sum A_1 + A_2 + \ldots + A_{N/2}. Let this sum equal S.
Let’s also look at a few lower indices. Working out the algebra is left as an exercise to the reader (it’s not hard, just write stuff out on paper).
- i = N-1 tells us that Q_{N-1} = (N-1)\cdot S.
Once again, since Q_{N-1} can’t be changed, if this isn’t true then no solution exists. - i = N-2 tells us that Q_{N-2} = (N-3)\cdot S - A_1 = (N-3)\cdot S + Q_1
- i = N-3 tells us that Q_{N-3} = (N-5)\cdot S - 2A_1 - A_2 = (N-5)\cdot S + Q_2
- i = N-4 tells us that Q_{N-4} = (N-7)\cdot S - 3A_1 - 2A_2 - A_3 = (N-7)\cdot S + Q_3
\vdots
More generally, it can be seen that for 0 \leq i \lt \frac{N}{2}, Q_{N-1-i} - Q_i = (N-2i-1)\cdot S will hold (once again, this is only when A is a palindrome).
Recall that S is a constant, and we’re allowed to change any element of Q as we like (except for its last two elements; but those have been considered already).
So, for any i such that Q_{N-1-i} - Q_i \neq (N-2i-1)\cdot S, we need to use one move (say on Q_i) to make this equation true.
This tells us the minimum number of moves we need.
It’s not hard to verify that for an array Q that satisfies these properties, the resulting array A is a palindrome.
That takes care of the case where N is even.
When N is odd, a very similar analysis works, just that this time you have the “middle” element A_{(N+1)/2} to deal with too.
Let N = 2K+1.
Following the same steps will tell you that
Q_N = (K+1)\cdot (2A_1 + 2A_2 + \ldots + 2A_{(N-1)/2} + A_{(N+1)/2}), which fixes
S = (2A_1 + 2A_2 + \ldots + 2A_{(N-1)/2} + A_{(N+1)/2}) as a constant.
Just as in the even case, there’s one index whose value can’t be changed: Q_{N-1}.
If Q_{N-1} \neq S\cdot K, no solution exists.
Otherwise, looking at lower indices will tell you that Q_{N-1-i} - Q_i = (K-i) \cdot S should hold for each 0 \leq i \lt K, so simply count the number of indices where this fails.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
const db eps=1e-2;
int T,n;
int a[N];
db S[N],SS[N];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
S[0]=0;
for(int i=1;i<=n;i++) S[0]-=a[i];
S[0]/=2.0;
for(int i=1;i<=n;i++) S[i]=S[i-1]+a[i];
SS[0]=S[0];
for(int i=1;i<=n;i++) SS[i]=SS[i-1]+S[i];
if(abs(SS[n])>eps) printf("-1\n");
else
{
int ans=0;
for(int i=0,j=n-1;i<j;i++,j--) ans+=(abs(SS[i]-SS[j])>eps);
if(SS[0]!=SS[n-1]) ans=-1;
printf("%d\n",ans);
}
}
return 0;
}
Tester's code (C++)
// Input Checker
// Input verification
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
#define lld long double
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readIntVec(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
else readEoln();
}
return v;
}
auto readLongVec(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
else readEoln();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
lld eps = 1e-9;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
// input_checker inp;
// int t = inp.readInt(1, 1e5); inp.readEoln();
int t;
cin>>t;
int sum_n = 0;
while (t--) {
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
lld a1[n+1], a2[n+2];
a1[0]=0;
for(int i=1;i<=n;i++)
a1[0]-=a[i-1];
a1[0]/=(lld)2.0;
for(int i=1;i<=n;i++)
a1[i]=a1[i-1]+a[i-1];
a2[0]=a1[0];
for(int i=1;i<=n;i++)
a2[i]=a2[i-1]+a1[i];
if(abs(a2[n])>eps)
cout<<-1<<"\n";
else
{
int ans=0;
for(int i=0,j=n-1;i<j;i++,j--)
{
ans+=(abs(a2[i]-a2[j])>eps);
lld dif=abs(a2[i]-a2[j]);
assert(abs(round(dif)-dif)<eps);
}
cout<<ans<<"\n";
}
}
// inp.readEof();
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
p = [0]
for x in a: p.append(x + p[-1])
q = [0]
for x in p[1:]: q.append(x + q[-1])
ans = 0
if n%2 == 0:
s = q[-1] // (n+1)
for i in range(n//2):
if q[n-1-i] - q[i] != s*(n - 2*i - 1): ans += 1
if q[-1] % (n+1) != 0 or q[-2] != (n-1)*s: ans = -1
else:
k = n//2
s = q[-1] // (k+1)
for i in range(k):
if q[n-1-i] - q[i] != s*(k-i): ans += 1
if q[-1] % (k+1) != 0 or q[-2] != k*s: ans = -1
print(ans)