EQSARRAY - Editorial

editorial
,
1

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')
2

@iceknight1093 Why do I need to separately check for N=1 scenario? As long as K is in the array, the program should work.
I see some wrong answers without this explicit check. Wondering in what cases can it fail

3

Notice that there are 2 No cases:

  • First, if K isn’t in the array at all
  • Second, if K is in the array, but only present as the last element

If N = 1 and the only element in the array is K, then the second case evaluates to True, right? After all, the only occurrence of K in the array is the last element.

But in this case, the answer should obviously be Yes, which is why you need to check for it separately.