Tiles Comeback (Codeforces 1851C)
Tags: Greedy, greedy

Vlad remembered that he had a series of $$$n$$$ tiles and a number $$$k$$$. The tiles were numbered from left to right, and the $$$i$$$-th tile had colour $$$c_i$$$.If you stand on the first tile and start jumping any number of tiles right, you can get a path of length $$$p$$$. The length of the path is the number of tiles you stood on.Vlad wants to see if it is possible to get a path of length $$$p$$$ such that:   it ends at tile with index $$$n$$$;  $$$p$$$ is divisible by $$$k$$$  the path is divided into blocks of length exactly $$$k$$$ each;  tiles in each block have the same colour, the colors in adjacent blocks are not necessarily different. For example, let $$$n = 14$$$, $$$k = 3$$$.The colours of the tiles are contained in the array $$$c$$$ = [$$$\color{red}{1}, \color{violet}{2}, \color{red}{1}, \color{red}{1}, \color{gray}{7}, \color{orange}{5}, \color{green}{3}, \color{green}{3}, \color{red}{1}, \color{green}{3}, \color{blue}{4}, \color{blue}{4}, \color{violet}{2}, \color{blue}{4}$$$]. Then we can construct a path of length $$$6$$$ consisting of $$$2$$$ blocks:$$$\color{red}{c_1} \rightarrow \color{red}{c_3} \rightarrow \color{red}{c_4} \rightarrow \color{blue}{c_{11}} \rightarrow \color{blue}{c_{12}} \rightarrow \color{blue}{c_{14}}$$$All tiles from the $$$1$$$-st block will have colour $$$\color{red}{\textbf{1}}$$$, from the $$$2$$$-nd block will have colour $$$\color{blue}{\textbf{4}}$$$.It is also possible to construct a path of length $$$9$$$ in this example, in which all tiles from the $$$1$$$-st block will have colour $$$\color{red}{\textbf{1}}$$$, from the $$$2$$$-nd block will have colour $$$\color{green}{\textbf{3}}$$$, and from the $$$3$$$-rd block will have colour $$$\color{blue}{\textbf{4}}$$$.

Input: The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$)—the number of tiles in the series and the length of the block.The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — the colours of the tiles.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output on a separate line:   YES if you can get a path that satisfies these conditions;  NO otherwise. You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).

Note: In the first test case, you can jump from the first tile to the last tile;The second test case is explained in the problem statement.

Sample Inputs:
10
4 2
1 1 1 1
14 3
1 2 1 1 7 5 3 3 1 3 4 4 2 4
3 3
3 1 3
10 4
1 2 1 2 1 2 1 2 1 2
6 2
1 3 4 1 6 6
2 2
1 1
4 2
2 1 1 1
2 1
1 2
3 2
2 2 2
4 1
1 1 2 2

Sample Outputs:
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES

Solution (Python):
t = int(input())
ans = []
for i in range(t):
    (n, k) = map(int, input().split())
    l = list(map(int, input().split()))
    if l.count(l[-1]) < k or l.count(l[0]) < k:
        ans.append('NO')
        continue
    if l[0] == l[-1]:
        ans.append('YES')
        continue
    c = 0
    color = l[0]
    for j in range(len(l)):
        if l[j] == color:
            c += 1
        if c == k:
            break
    if l[j + 1:].count(l[-1]) >= k:
        ans.append('YES')
    else:
        ans.append('NO')
for i in ans:
    print(i)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter, deque

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def solve():
    (n, k) = invr()
    c = inlt()
    possible = True
    (first, last) = (c[0], c[-1])
    count = 0
    last_count_idx = 0
    for i in range(n):
        if c[i] == first:
            count += 1
        if count == k:
            last_count_idx = i
            break
    if count < k:
        print('NO')
        return
    count = 0
    for i in range(n - 1, -1, -1):
        if c[i] == last:
            count += 1
        if count == k:
            if i > last_count_idx:
                print('YES')
                return
            elif first == last:
                print('YES')
                return
    print('NO')

def main():
    for _ in range(inp()):
        solve()
main()

Solution (Python):
import sys

def get_ints():
    return map(int, sys.stdin.readline().strip().split())

def get_list():
    return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
    return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
    return sys.stdin.readline().strip()

def get_int():
    return int(sys.stdin.readline().strip())

def get_print_int(x):
    sys.stdout.write(str(x) + '\n')

def get_print(x):
    sys.stdout.write(x + '\n')

def get_print_int_same(x):
    sys.stdout.write(str(x) + ' ')

def get_print_same(x):
    sys.stdout.write(x + ' ')
from sys import maxsize
from math import sqrt, floor
tt = int(input())

def check(arr, k):
    n = len(arr)
    first = arr[0]
    last = arr[n - 1]
    count = 0
    ind = -1
    for i in range(0, n):
        if first == arr[i]:
            count += 1
        if count == k:
            ind = i
            break
    if ind == -1:
        return False
    count = 0
    for i in range(ind + 1, n):
        if arr[i] == last:
            count += 1
        if count == k:
            return True
    return False

def solve():
    l1 = get_list()
    l2 = get_list()
    n = l1[0]
    k = l1[1]
    first = l2[0]
    last = l2[len(l2) - 1]
    ans = None
    if first != last:
        flag = check(l2, k)
        if flag:
            ans = 'YES'
        else:
            ans = 'NO'
    else:
        m = dict()
        count = 0
        for i in range(0, n):
            if first == l2[i]:
                count += 1
        if count >= k:
            ans = 'YES'
        else:
            ans = 'NO'
    print(ans)
while tt > 0:
    solve()
    tt -= 1