KPAL - Editorial


Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: jeevanjyot
Testers: iceknight1093, rivalq
Editorialist: iceknight1093






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?


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.


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!


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.


\mathcal{O}(N) per test case.


Setter's code (C++)
#ifdef WTSH
    #include <wtsh.h>
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)

#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;
        char g = getchar();
        if(g == '-')
            assert(fi == -1);
            is_neg = true;
        if('0' <= g && g <= '9')
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        else if(g == endd)
                x = -x;
            if(!(l <= x && x <= r))
                cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
            return x;

string readString(int l, int r, char endd)
    string ret = "";
    int cnt = 0;
        char g = getchar();
        assert(g != -1);
        if(g == endd)
        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";
        if(k == n)
            cout << "NO\n";
        else if(n % 2 == 1 or k % 2 == 1)
            cout << "YES\n";
            int sum = accumulate(a.begin(), a.end(), 0LL);
            if(sum % 2 == 0)
                cout << "YES\n";
                cout << "NO\n";

int32_t main()
    int T = readIntLn(1, 1e5);
    for(int tc = 1; tc <= T; tc++)
        // cout << "Case #" << tc << ": ";
    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')
	if n%2 == 1 or k%2 == 1:
	print('Yes' if sum(a)%2 == 0 else 'No')

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…

MY SOLUTION : CodeChef | Competitive Programming | Participate & Learn

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?