PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Reyaan Jagnani
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
1280
PREREQUISITES:
None
PROBLEM:
You have an array of N integers and an integer K. In one move, you can choose any subarray and make every element of this subarray equal to the middle element (the left one, if length is even).
Can you make every element equal K?
EXPLANATION:
If some value is not in the array, there’s no way to bring it into the array. So, if A doesn’t contain K, the answer is immediately No
.
So, suppose A contains K. In particular, suppose A_i = K. Then,
- If i+1 \lt N, then choosing the subarray [i, i+1] allows us to set A_{i+1} = K.
- If 1 \lt i \lt N-1, then choosing the subarray [i-1, i+1] allows us to set A_{i-1} = A_{i+1} = K.
In particular, if we have a K at some position i:
- Every position after i can be made K.
- Every position before i can be made K as long as i+1 \lt N.
So, if there exists a position i \lt N such that A_i = K, then the answer is immediately Yes
.
That leaves us with the case when A_N = K, and this is the only K in the array. It’s not hard to see that in this case, no other element can ever be made K.
Thus, the answer in this case is Yes
if N = 1 and No
otherwise.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
print('No' if (n > 1 and a[:n-1].count(k) == 0) or a.count(k) == 0 else 'Yes')