Maxmina
Contest: Codeforces Global Round 23
Difficulty rating: 800
Tags: constructive algorithms, greedy

You have an array $$$a$$$ of size $$$n$$$ consisting only of zeroes and ones and an integer $$$k$$$. In one operation you can do one of the following:

- Select $$$2$$$ consecutive elements of $$$a$$$ and replace them with their minimum (that is, let $$$a := [a_{1}, a_{2}, \ldots, a_{i-1}, \min(a_{i}, a_{i+1}), a_{i+2}, \ldots, a_{n}]$$$ for some $$$1 \le i \le n-1$$$). This operation decreases the size of $$$a$$$ by $$$1$$$.
- Select $$$k$$$ consecutive elements of $$$a$$$ and replace them with their maximum (that is, let $$$a := [a_{1}, a_{2}, \ldots, a_{i-1}, \max(a_{i}, a_{i+1}, \ldots, a_{i+k-1}), a_{i+k}, \ldots, a_{n}]$$$ for some $$$1 \le i \le n-k+1$$$). This operation decreases the size of $$$a$$$ by $$$k-1$$$.

Determine if it's possible to turn $$$a$$$ into $$$[1]$$$ after several (possibly zero) operations.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 50$$$), the size of array $$$a$$$ and the length of segments that you can perform second type operation on.

The second line contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$a_i$$$ is $$$0$$$ or $$$1$$$), elements of array $$$a$$$.

Output format:
For each test case, if it is possible to turn $$$a$$$ into $$$[1]$$$, print "YES", otherwise print "NO".

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can perform the second type operation on second and third elements so $$$a$$$ becomes $$$[0, 1]$$$, then you can perform the second type operation on first and second elements, so $$$a$$$ turns to $$$[1]$$$.

In the fourth test case, it's obvious to see that you can't make any $$$1$$$, no matter what you do.

In the fifth test case, you can first perform a type 2 operation on the first three elements so that $$$a$$$ becomes $$$[1, 0, 0, 1]$$$, then perform a type 2 operation on the elements in positions two through four, so that $$$a$$$ becomes $$$[1, 1]$$$, and finally perform the first type operation on the remaining elements, so that $$$a$$$ becomes $$$[1]$$$.

Example input:
7
3 2
0 1 0
5 3
1 0 1 1 0
2 2
1 1
4 4
0 0 0 0
6 3
0 0 1 0 0 1
7 5
1 1 1 1 1 1 1
5 3
0 0 1 0 0

Example output:
YES
YES
YES
NO
YES
YES
YES

Editorial:
Step 1: It's obvious that the answer is "NO" if $$$a_{i} = 0$$$ for all $$$1 \le i \le n$$$.
Step 2: Lets prove that the answer is "YES" if $$$a_{i} = 1$$$ for at least one $$$1 \le i \le n$$$.
Step 3: If size of $$$a$$$ is equal to $$$k$$$, just use second type operation once and we are done.
Step 4: Otherwise (if $$$|a| > k$$$), there will be three cases: (assume that $$$a_{j} = 1$$$)
1. if $$$j > 2$$$, you can use first type operation on first and second element and decrease size of $$$a$$$ by 1.
2. else if $$$j < |a|-1$$$, you can use first type operation on last and second to last element and decrease size of $$$a$$$ by 1.
3. else, it can be shown easily that $$$|a| = 3$$$ and $$$k = 2$$$ so you can use second type operation twice and turn $$$a$$$ into a single $$$1$$$.
In first and second case, you can continue decreasing size of $$$a$$$ until $$$|a| = k$$$ (or you reach $$$3$$$-rd case) and you can use second type operation to reach your aim.
Step 5: So we proved that the answer is "YES" iff $$$a_{i} = 1$$$ for at least one $$$1 \le i \le n$$$ or in other words, iff $$$\sum_{i = 1}^n a_{i} > 0$$$.