 # KPAL - Editorial

Author: jeevanjyot
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

TBD

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, ' '); }
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[n - 1] = readIntLn(l, r);
return a;
}

// -------------------- Input Checker End --------------------

int sumN = 0;

void solve()
{
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);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
assert(sumN <= 2e5);
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')

3 Likes

Hi, I have written the code exactly similar to the approach given in the editorial, I had done almost 7-8 submissions, but I seem to fail only one test case. I also generated random inputs on my local machine and then compared the output with the correct submission. I got exactly same output as correct code. I am confused why my code is not getting AC…

Why is it failing ???

The K = N case in your code is wrong.
You’re checking whether A can be rearranged into a palindrome, but that’s not enough. K = N is only solvable when the array is already a palindrome.

Simple example: K=N=3, A = [1, 2, 2].

thanks… helps… @iceknight1093 .

Sir Is this question can be done by only by observation?
Or we can solve it by any other method?