PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given an array A, you can repeatedly insert the integer K into it at any position you like.
Is it possible to turn A into a palindrome?
EXPLANATION:
To solve this problem, it’s helpful to look at the elements of the array that are not equal to K.
Let B denote the array formed by taking the non-K elements of array A.
For example, if A = [1, 2, 3, 1, 3, 2] and K = 3, then we’ll have B = [1, 2, 1, 2].
Inserting copies of K into the array A cannot affect the relative order of elements in B.
Now, to turn the array A into a palindrome, we need to match elements from the front and the back.
Inserted elements (i.e. copies of K) can only match with copies of K, which means all other elements have to match among themselves.
So, if the array B is itself a palindrome, then it’s possible to turn A into a palindrome by just inserting copies of K appropriately.
For instance, say A = [1, 2, 3, 2, 3, 1] and K = 3 so that B = [1, 2, 2, 1] is a palindrome.
We can then insert copies of 3 into A to form [1, 3, 2, 3, 2, 3, 1] which is a palindrome.
On the other hand, if B is not a palindrome, then it’s impossible to turn A into a palindrome.
This is because, as noted earlier, elements other than K must match among themselves.
But if B is not a palindrome then this matching will break down at some point, and we cannot fix it with copies of K.
Thus, the answer is Yes if B is a palindrome, and No otherwise.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
other = []
for x in a:
if x != k: other.append(x)
if other == list(reversed(other)):
print('Yes')
else:
print('No')