Binary Literature (Codeforces 1509D)
Tags: Greedy, strings

A bitstring is a string that contains only the characters 0 and 1.Koyomi Kanou is working hard towards her dream of becoming a writer. To practice, she decided to participate in the Binary Novel Writing Contest. The writing prompt for the contest consists of three bitstrings of length $$$2n$$$. A valid novel for the contest is a bitstring of length at most $$$3n$$$ that contains at least two of the three given strings as subsequences.Koyomi has just received the three prompt strings from the contest organizers. Help her write a valid novel for the contest.A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero) characters.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).Each of the following three lines contains a bitstring of length $$$2n$$$. It is guaranteed that these three strings are pairwise distinct.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output: For each test case, print a single line containing a bitstring of length at most $$$3n$$$ that has at least two of the given bitstrings as subsequences.It can be proven that under the constraints of the problem, such a bitstring always exists.If there are multiple possible answers, you may output any of them.

Note: In the first test case, the bitstrings 00 and 01 are subsequences of the output string: 010 and 010. Note that 11 is not a subsequence of the output string, but this is not required.In the second test case all three input strings are subsequences of the output string: 011001010, 011001010 and 011001010.

Sample Inputs:
2
1
00
11
01
3
011001
111010
010001

Sample Outputs:
010
011001010

Solution (Python):
def merge(x, y, c):
    N = len(x)
    n = N // 2
    ans = ''
    (i, j) = (0, 0)
    while i < N and j < N:
        if x[i] == y[j]:
            ans += x[i]
            i += 1
            j += 1
        elif x[i] != c:
            ans += x[i]
            i += 1
        else:
            ans += y[j]
            j += 1
    ans += x[i:] + y[j:]
    ans += '0' * (3 * n - len(ans))
    return ans
for _ in range(int(input())):
    n = int(input())
    S = [input(), input(), input()]
    C0 = [j for j in range(3) if S[j].count('0') >= n]
    if len(C0) >= 2:
        print(merge(S[C0[0]], S[C0[1]], '0'))
    else:
        C1 = [j for j in range(3) if j not in C0]
        print(merge(S[C1[0]], S[C1[1]], '1'))

Solution (Python):
import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

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

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

def input():
    return sys.stdin.readline().strip()
mod = 10 ** 9 + 7

def mix(s, t, c):
    n = len(s) // 2
    (v1, v2) = ([-1], [-1])
    for i in range(2 * n):
        if s[i] == c:
            v1.append(i)
        if t[i] == c:
            v2.append(i)
    ans = ''
    for i in range(n):
        for j in range(v1[i] + 1, v1[i + 1]):
            ans += s[j]
        for j in range(v2[i] + 1, v2[i + 1]):
            ans += t[j]
        ans += c
    for j in range(v1[n] + 1, 2 * n):
        ans += s[j]
    for j in range(v2[n] + 1, 2 * n):
        ans += t[j]
    return ans
for _ in range(int(input())):
    n = int(input())
    a = input()
    b = input()
    c = input()
    (s0, s1) = ([], [])
    if a.count('0') >= n:
        s0.append(a)
    else:
        s1.append(a)
    if b.count('0') >= n:
        s0.append(b)
    else:
        s1.append(b)
    if c.count('0') >= n:
        s0.append(c)
    else:
        s1.append(c)
    if len(s0) >= 2:
        print(mix(s0[0], s0[1], '0'))
    else:
        print(mix(s1[0], s1[1], '1'))

Solution (Python):
from math import gcd
from collections import defaultdict as dd
MOD = 10 ** 9 + 7

def R(type=int):
    line = input().rstrip()
    try:
        return type(line)
    except:
        pass
    return line
RL = lambda type=int: list(map(type, input().rstrip().split()))
RLL = lambda N, type=int: [RL(type) for _ in range(N)]
RLS = lambda N, type=int: [R(type) for _ in range(N)]

def test0(s0, s1):
    s = ''
    i = 0
    for c in s0:
        if c == '0':
            while i < len(s1) and s1[i] == '1':
                s += '1'
                i += 1
            if i < len(s1):
                i += 1
        s += c
    while i < len(s1):
        s += s1[i]
        i += 1
    print(s)

def test1(s0, s1):
    s = ''
    i = 0
    for c in s0:
        if c == '1':
            while i < len(s1) and s1[i] == '0':
                s += '0'
                i += 1
            if i < len(s1):
                i += 1
        s += c
    while i < len(s1):
        s += s1[i]
        i += 1
    print(s)

def solve():
    n = R()
    A = RLS(3, str)
    o0 = A[0].count('1')
    z0 = 2 * n - o0
    o1 = A[1].count('1')
    z1 = 2 * n - o1
    o2 = A[2].count('1')
    z2 = 2 * n - o2
    if o0 >= n:
        if o1 >= n:
            test1(A[0], A[1])
            return
        if o2 >= n:
            test1(A[0], A[2])
            return
    else:
        if z1 >= n:
            test0(A[0], A[1])
            return
        if z2 >= n:
            test0(A[0], A[2])
            return
    if o1 >= n:
        test1(A[1], A[2])
    else:
        test0(A[1], A[2])
T = R()
for t in range(T):
    solve()