PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: jeevanjyot
Testers: iceknight1093, rivalq
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Observation
PROBLEM:
You have an array A and an integer K.
In one move, you can choose exactly K elements of A and increase their values by 1.
Is is possible to make A a palindrome?
EXPLANATION:
Let’s get a trivial edge-case out of the way first:
If K = N then we can only increase every element. In this case, if A isn’t already a palindrome it’s obviously impossible to turn it into one.
From now on, we’ll assume K \lt N.
Our objective now is to make A_i = A_{N+1-i} for every 1 \leq i \leq N.
In particular, if A_i \lt A_{N+1-i}, we need to increase it by (A_{N+1-i} - A_i).
After that’s achieved, A_i and A_{N+1-i} need to be increased by equal amounts, to preserve their equality.
When either N or K is odd, it can be seen that it’s always possible to make A a palindrome.
How?
First, say K is odd.
We have the following simple strategy:
- If A_i = A_{N+1-i} for every i, we’re done.
- Otherwise, pick an index i such that A_i \lt A_{N+1-i}
- Next, choose \frac{K-1}{2} pairs of opposite indices that don’t include N+1-i (which is always possible since K \lt N), for a total of K indices chosen.
- Perform the operation on these K indices, and continue.
Each move brings A_i closer to A_{N+1-i}, while not breaking the ‘palindrome-ness’ of all other indices.
It’s not hard to see that it’ll finish in finite time, at which point we’ll be done.
Next, say N is odd and K is even.
Once again we have a similar strategy:
- Pick an index i such that A_i \lt A_{N+1-i}
- Pick the middle index, which can be increased freely
- Finally, pick \frac{K-2}{2} pairs of opposite indices excluding N+1-i (once again, always possible since K \lt N) and perform the operation on these K.
This leaves us with the case when N is even, K is even, and K \lt N.
Note that:
- Since N is even, if the final array is a palindrome its sum will be even.
- Since K is even, each move increases the sum of the array by an even number.
Together, this tells us that if sum(A) is odd, it can never be turned into a palindrome.
What if sum(A) is even?
We can always make A into a palindrome!
Proof
This can be proved with a minor modification to our proofs odd K and N.
Consider the following process:
- If A_i = A_{N+1-i} for every i, we’re done.
- Otherwise, find an index i such that A_i \lt A_{N+1-i}.
- There are now two possible cases.
- If there exists another index j such that A_j \lt A_{N+1-j}, then pick j as well, then pick \frac{K-2}{2} opposite pairs not including these two and perform the operation on them.
- If no such j exists, then the sum of the array being even means that A_i+2 \leq A_{N+1-i}.
- So, pick an arbitrary index j (that is not N+1-i), and \frac{K-2}{2} more opposite pairs and perform the operation on them.
- Next, pick i, N+1-j, and then \frac{K-2}{2} more pairs to perform the operation.
- This way we’ve increased A_i by 2 while preserving ‘palindrome-ness’ of the other indices.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
const long long INF = 1e18;
const int N = 1e6 + 5;
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
int sumN = 0;
void solve()
{
int n = readIntSp(1, 1e5);
int k = readIntLn(1, n);
sumN += n;
vector<int> a = readVectorInt(n, 1, 1e6);
vector<int> b = a;
reverse(b.begin(), b.end());
if(a == b)
cout << "YES\n";
else
{
if(k == n)
cout << "NO\n";
else if(n % 2 == 1 or k % 2 == 1)
cout << "YES\n";
else
{
int sum = accumulate(a.begin(), a.end(), 0LL);
if(sum % 2 == 0)
cout << "YES\n";
else
cout << "NO\n";
}
}
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 1e5);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
assert(sumN <= 2e5);
readEOF();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
if n == k:
print('Yes' if a == a[::-1] else 'No')
continue
if n%2 == 1 or k%2 == 1:
print('Yes')
continue
print('Yes' if sum(a)%2 == 0 else 'No')