Two 0-1 Sequences (Codeforces 1704A)
Tags: Greedy, constructive algorithms

AquaMoon has two binary sequences $$$a$$$ and $$$b$$$, which contain only $$$0$$$ and $$$1$$$. AquaMoon can perform the following two operations any number of times ($$$a_1$$$ is the first element of $$$a$$$, $$$a_2$$$ is the second element of $$$a$$$, and so on): Operation 1: if $$$a$$$ contains at least two elements, change $$$a_2$$$ to $$$\operatorname{min}(a_1,a_2)$$$, and remove the first element of $$$a$$$. Operation 2: if $$$a$$$ contains at least two elements, change $$$a_2$$$ to $$$\operatorname{max}(a_1,a_2)$$$, and remove the first element of $$$a$$$.Note that after a removal of the first element of $$$a$$$, the former $$$a_2$$$ becomes the first element of $$$a$$$, the former $$$a_3$$$ becomes the second element of $$$a$$$ and so on, and the length of $$$a$$$ reduces by one.Determine if AquaMoon can make $$$a$$$ equal to $$$b$$$ by using these operations.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\,000$$$) — the number of test cases. Description of test cases follows.The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n,m \leq 50$$$, $$$m \leq n$$$) — the lengths of $$$a$$$ and $$$b$$$ respectively.The second line of each test case contains a string $$$a$$$ of length $$$n$$$, consisting only $$$0$$$ and $$$1$$$.The third line of each test case contains a string $$$b$$$ of length $$$m$$$, consisting only $$$0$$$ and $$$1$$$.

Output: For each test case, output "YES" if AquaMoon can change $$$a$$$ to $$$b$$$ by using these options; otherwise, output "NO".You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as a positive answer).

Note: In the first test case, you can use Operation 2 four times to make $$$a$$$ equals to $$$b$$$.In the second test case, you can use Operation 1 four times to make $$$a$$$ equals to $$$b$$$.In the third test case, it can be proved that no matter how we use the operations, it is impossible to make $$$a$$$ equal to $$$b$$$.In the fourth test case, it can be proved that no matter how we use the operations, it is impossible to make $$$a$$$ equal to $$$b$$$.In the fifth test case, you can use Operation 2 three times to make $$$a$$$ become $$$10101$$$, so the first element of $$$a$$$ equals to the first element of $$$b$$$, but it can be proved that no matter how to operate, the second to the fifth elements of $$$a$$$ can't be the same as $$$b$$$.

Sample Inputs:
10
6 2
001001
11
6 2
110111
01
6 2
000001
11
6 2
111111
01
8 5
10000101
11010
7 4
1010001
1001
8 6
01010010
010010
8 4
01010101
1001
8 4
10101010
0110
7 5
1011100
11100

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

Solution (Python):
for t in range(int(input())):
    (n, m) = map(int, input().split())
    a = str(input())
    b = str(input())
    if m == 1:
        if b in a:
            print('YES')
        else:
            print('NO')
    elif b[0] in a[:n - m + 1] and b[1:] == a[n - m + 1:]:
        print('YES')
    else:
        print('NO')

Solution (Python):
def solve():
    (size_a, size_b) = map(int, input().split())
    a = input()
    b = input()
    if a[size_a - size_b + 1:] == b[1:]:
        if b[0] == '0' and '0' in a[:size_a - size_b + 1]:
            print('YES')
        elif b[0] == '1' and '1' in a[:size_a - size_b + 1]:
            print('YES')
        else:
            print('NO')
    else:
        print('NO')
if __name__ == '__main__':
    for test in range(int(input())):
        solve()

Solution (Python):
from sys import stdin, stdout

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

def PRINT(s):
    stdout.write(s + '\n')

def logic(n, m, a, b):
    if n < m:
        return 'NO'
    if m > 1:
        if a[-m + 1:] != b[-m + 1:]:
            return 'NO'
        a = a[:-m + 1]
    if b[-m] == '0':
        if '0' in a:
            return 'YES'
        return 'NO'
    else:
        if '1' in a:
            return 'YES'
        return 'NO'
for w in range(int(stdin.readline())):
    (n, m) = get_ints()
    a = stdin.readline()[:-1]
    b = stdin.readline()[:-1]
    PRINT(logic(n, m, a, b))