Overview

This is a problem of determining whether there exists a position in a sequence of length \(N\) where the same value appears \(K\) or more times consecutively.

Analysis

Key Insight

A naive approach would be to check, for every starting position \(l\), whether all elements in the interval \([l, l+K-1]\) are the same. However, this requires up to \(K\) comparisons per interval, resulting in \(O(NK)\) overall, which is inefficient when \(N\) or \(K\) is large.

The key insight here is that it is sufficient to scan through the sequence once while counting how many consecutive elements have the same value.

Understanding with a Concrete Example

Consider the case where \(N = 7\), \(K = 3\), and the heights are [3, 3, 5, 5, 5, 5, 2].

Position \(i\)	\(H_i\)	Consecutive Count
1	3	1
2	3	2
3	5	1 (reset)
4	5	2
5	5	3 ← \(\geq K\)!

At position 5, the count reaches \(3 \geq K\), so we can determine that a flat interval exists.

Special Case When \(K = 1\)

When \(K = 1\), an interval of length 1 is flat at any position, so as long as \(N \geq 1\), the answer is always Yes.

Algorithm

1. If \(K = 1\), immediately answer Yes.
2. Otherwise, initialize a variable count to \(1\), and scan from position \(2\) to position \(N\) in order.
3. If the height at position \(i\) is the same as at position \(i-1\), increment count by \(1\). If different, reset it (count = 1).
4. As soon as count reaches \(K\) or more, a flat interval has been found, so output Yes and terminate.
5. If no such interval is found after scanning the entire sequence, output No.

This approach is based on a “run-length” concept, where we track the length of consecutive runs of the same value.

Complexity

• Time complexity: \(O(N)\) — only a single pass through the array
• Space complexity: \(O(N)\) — for storing the input array (the variables used for scanning are \(O(1)\))

Implementation Notes

• Initial value of count is \(1\): Since position 1 itself forms a consecutive run of length 1, we start from \(1\), not \(0\).

• Don’t forget to reset on adjacent comparison: When \(H_i \neq H_{i-1}\), reset count = 1. Setting it to \(0\) would be incorrect (because the current position itself is the start of a new consecutive run, so it should be \(1\)).

• Early termination: By using break the moment count >= K is satisfied, we can avoid unnecessary scanning. However, the worst-case complexity remains the same.

  Source Code

N, K = map(int, input().split())
H = [int(input()) for _ in range(N)]

count = 1
found = False
if K == 1:
    found = True
else:
    for i in range(1, N):
        if H[i] == H[i-1]:
            count += 1
            if count >= K:
                found = True
                break
        else:
            count = 1

print("Yes" if found else "No")

---

This editorial was generated by claude4.6opus-thinking.