UPDWPAL - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given an array A of length N.
You can do the following operation at most once:

  • Choose a value X, then add 1 to every element that’s \le X and subtract 1 from every element that’s \gt X.

Can the array be turned into a palindrome?

EXPLANATION:

If we decide on a value of X, it’s quite easy to just compute the transformed array and then check if it’s a palindrome.
The question is, which value of X should we choose?

To answer that, we look at the condition for an array being a palindrome: A_i = A_{N+1-i} for every i.

So, suppose that there’s some index i such that A_i \ne A_{N+1-i}.
Without loss of generality, let A_i \lt A_{N+1-i}.

Our only hope of making A_i = A_{N+1-i} now, is to increase A_i by 1 and decrease A_{N+1-i} by 1.
This is because, if they both increase/both decrease, they’ll remain different values.

Thus we definitely need A_i+1 = A_{N+1-i}-1, meaning A_{N+1-i} - A_i = 2.
That is, the two values differ by 2.
If this doesn’t hold, certainly no choice of X can make this opposite pair equal so we can immediately output No.

Otherwise, we do have A_{N+1-i} - A_i = 2.
Now observe that the only values of X that could possibly work are A_i and A_i+1.
This is because:

  • If X \lt A_i then both A_i and A_{N+1-i} will increase.
  • If X \ge A_{N+1-i} then both A_i and A_{N+1-i} will decrease.

So, simply check for the two values X = A_i and X = A_i+1.
If either of them results in a palindrome, the answer is Yes. Otherwise the answer is No.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ans = 'Yes'
    for i in range(n):
        if a[i] == a[n-1-i]: continue
        
        ans = 'No'
        mn = min(a[i], a[n-1-i])
        for x in [mn, mn+1]:
            b = [a[j]+1 if a[j] <= x else a[j]-1 for j in range(n)]
            if b == list(reversed(b)): ans = 'Yes'
        break
    print(ans)