Binary String Reconstruction (Codeforces 1400C)
Tags: Greedy, 2-sat

Consider the following process. You have a binary string (a string where each character is either 0 or 1) $$$w$$$ of length $$$n$$$ and an integer $$$x$$$. You build a new binary string $$$s$$$ consisting of $$$n$$$ characters. The $$$i$$$-th character of $$$s$$$ is chosen as follows:  if the character $$$w_{i-x}$$$ exists and is equal to 1, then $$$s_i$$$ is 1 (formally, if $$$i > x$$$ and $$$w_{i-x} = $$$ 1, then $$$s_i = $$$ 1);  if the character $$$w_{i+x}$$$ exists and is equal to 1, then $$$s_i$$$ is 1 (formally, if $$$i + x \le n$$$ and $$$w_{i+x} = $$$ 1, then $$$s_i = $$$ 1);  if both of the aforementioned conditions are false, then $$$s_i$$$ is 0. You are given the integer $$$x$$$ and the resulting string $$$s$$$. Reconstruct the original string $$$w$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.Each test case consists of two lines. The first line contains the resulting string $$$s$$$ ($$$2 \le |s| \le 10^5$$$, each character of $$$s$$$ is either 0 or 1). The second line contains one integer $$$x$$$ ($$$1 \le x \le |s| - 1$$$).The total length of all strings $$$s$$$ in the input does not exceed $$$10^5$$$.

Output: For each test case, print the answer on a separate line as follows:  if no string $$$w$$$ can produce the string $$$s$$$ at the end of the process, print $$$-1$$$;  otherwise, print the binary string $$$w$$$ consisting of $$$|s|$$$ characters. If there are multiple answers, print any of them. 


Sample Inputs:
3
101110
2
01
1
110
1

Sample Outputs:
111011
10
-1

Solution (Python):
def verifica(w, s):
    for j in range(x, tam - x):
        if s[j] == '1' and w[j + x] != '1' and (w[j - x] != '1'):
            return True
    for j in range(0, x):
        if s[j] == '1' and w[j + x] != '1':
            return True
    for j in range(tam - x, tam):
        if s[j] == '1' and w[j - x] != '1':
            return True
    return False
t = int(input())
for i in range(0, t):
    s = input()
    x = int(input())
    tam = len(s)
    teste = False
    w = ['1'] * tam
    if 2 * x > tam:
        for j in range(tam - x, x):
            if s[j] == '1':
                teste = True
                break
        if not teste:
            for j in range(0, tam - x):
                if s[j] == '0':
                    w[j + x] = '0'
            for j in range(x, tam):
                if s[j] == '0':
                    w[j - x] = '0'
    else:
        for j in range(x, tam - x):
            if s[j] == '0':
                w[j + x] = '0'
                w[j - x] = '0'
        if not teste:
            for j in range(0, x):
                if s[j] == '0':
                    w[j + x] = '0'
            for j in range(tam - x, tam):
                if s[j] == '0':
                    w[j - x] = '0'
        teste = verifica(w, s)
    if teste:
        print('-1')
    else:
        print(''.join(w))

Solution (Python):
for _ in range(int(input())):
    s = input()
    x = int(input())
    n = len(s)
    w = ['1'] * n
    for i in range(n):
        if s[i] == '0':
            if i - x >= 0:
                w[i - x] = '0'
            if i + x < n:
                w[i + x] = '0'
    for i in range(n):
        one = False
        one = one or (i - x >= 0 and w[i - x] == '1')
        one = one or (i + x < n and w[i + x] == '1')
        if s[i] != chr(one + 48):
            print(-1)
            break
    else:
        print(''.join(w))

Solution (Python):
a = int(input())
for k in range(a):
    (x, y) = (input(), int(input()))
    n = len(x)
    ans = ['1'] * len(x)
    for i in range(len(x)):
        if x[i] == '0':
            if i - y >= 0:
                ans[i - y] = '0'
            if i + y < n:
                ans[i + y] = '0'
    temp = 0
    for i in range(len(x)):
        if x[i] == '1':
            if i - y >= 0 and ans[i - y] == '1' or (i + y < n and ans[i + y] == '1'):
                temp = 0
            else:
                temp = 1
                break
    result = ''
    for i in ans:
        result += i
    if temp == 1:
        print(-1)
    else:
        print(result)