Binary Literature (Codeforces 1508A)
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):
import math
import random
import time
from collections import defaultdict
contor = 0
matricea = {}
alfabet = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26}
alfabet_2 = {'1': 'a', '2': 'b', '3': 'c', '4': 'd', '5': 'e', '6': 'f', '7': 'g', '8': 'h', '9': 'i', '10': 'j', '11': 'k', '12': 'l', '13': 'm', '14': 'n', '15': 'o', '16': 'p', '17': 'q', '18': 'r', '19': 's', '20': 't', '21': 'u', '22': 'v', '23': 'w', '24': 'x', '25': 'y', '26': 'z'}
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound

class FenwickTree:

    def __init__(self, x):
        bit = self.bit = list(x)
        size = self.size = len(bit)
        for i in range(size):
            j = i | i + 1
            if j < size:
                bit[j] += bit[i]

    def update(self, idx, x):
        """"""
        while idx < self.size:
            self.bit[idx] += x
            idx |= idx + 1

    def __call__(self, end):
        """"""
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x

    def find_kth(self, k):
        """"""
        idx = -1
        for d in reversed(range(self.size.bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < self.size and self.bit[right_idx] <= k:
                idx = right_idx
                k -= self.bit[idx]
        return (idx + 1, k)

class SortedList:
    block_size = 700

    def __init__(self, iterable=()):
        self.macro = []
        self.micros = [[]]
        self.micro_size = [0]
        self.fenwick = FenwickTree([0])
        self.size = 0
        for item in iterable:
            self.insert(item)

    def insert(self, x):
        i = lower_bound(self.macro, x)
        j = upper_bound(self.micros[i], x)
        self.micros[i].insert(j, x)
        self.size += 1
        self.micro_size[i] += 1
        self.fenwick.update(i, 1)
        if len(self.micros[i]) >= self.block_size:
            self.micros[i:i + 1] = (self.micros[i][:self.block_size >> 1], self.micros[i][self.block_size >> 1:])
            self.micro_size[i:i + 1] = (self.block_size >> 1, self.block_size >> 1)
            self.fenwick = FenwickTree(self.micro_size)
            self.macro.insert(i, self.micros[i + 1][0])

    def pop(self, k=-1):
        (i, j) = self._find_kth(k)
        self.size -= 1
        self.micro_size[i] -= 1
        self.fenwick.update(i, -1)
        return self.micros[i].pop(j)

    def __getitem__(self, k):
        (i, j) = self._find_kth(k)
        return self.micros[i][j]

    def count(self, x):
        return self.upper_bound(x) - self.lower_bound(x)

    def __contains__(self, x):
        return self.count(x) > 0

    def lower_bound(self, x):
        i = lower_bound(self.macro, x)
        return self.fenwick(i) + lower_bound(self.micros[i], x)

    def upper_bound(self, x):
        i = upper_bound(self.macro, x)
        return self.fenwick(i) + upper_bound(self.micros[i], x)

    def _find_kth(self, k):
        return self.fenwick.find_kth(k + self.size if k < 0 else k)

    def __len__(self):
        return self.size

    def __iter__(self):
        return (x for micro in self.micros for x in micro)

    def __repr__(self):
        return str(list(self))

def prime_generator(nr_elemente_prime):
    vector_prime = [-1] * nr_elemente_prime
    vector_rasp = [0] * nr_elemente_prime
    vector_prime[1] = 1
    vector_rasp[1] = 1
    contor = 2
    for i in range(2, nr_elemente_prime):
        if vector_prime[i] == -1:
            vector_prime[i] = 1
            vector_rasp[contor] = i
            contor = contor + 1
        for j in range(i + i, nr_elemente_prime, i):
            if vector_prime[j] == -1:
                vector_prime[j] = i
    set_prime = set(vector_rasp)
    set_prime.remove(0)
    set_prime.remove(1)
    answ_prime = list(set_prime)
    answ_prime.sort()
    return answ_prime

def binary_search(vectorul, valoarea):
    left = 0
    right = len(vectorul) - 1
    while left <= right:
        centru = (left + right) // 2
        if vectorul[centru][0] < valoarea:
            left = centru + 1
        else:
            right = centru - 1
    return left

def main():
    vec_answ = []
    kuri = []
    answ = []
    teste = int(input())
    contor_numere = 0
    for gg in range(teste):
        n = int(input())
        jumatate = n
        n *= 2
        stringul_unu = input()
        stringul_doi = input()
        stringul_trei = input()
        zero_unu = []
        zero_doi = []
        zero_trei = []
        unu_unu = []
        unu_doi = []
        unu_trei = []
        for i in range(n):
            if stringul_unu[i] == '1':
                unu_unu.append(i)
            else:
                zero_unu.append(i)
            if stringul_doi[i] == '1':
                unu_doi.append(i)
            else:
                zero_doi.append(i)
            if stringul_trei[i] == '1':
                unu_trei.append(i)
            else:
                zero_trei.append(i)
        if min(len(zero_unu), len(zero_doi)) >= jumatate:
            answ = ''
            cate = min(len(zero_unu), len(zero_doi))
            last_unu = 0
            last_doi = 0
            for i in range(cate):
                answ += stringul_unu[last_unu:zero_unu[i]]
                answ += stringul_doi[last_doi:zero_doi[i]]
                last_unu = zero_unu[i] + 1
                last_doi = zero_doi[i] + 1
                answ += '0'
            answ += stringul_unu[last_unu:len(stringul_unu)]
            answ += stringul_doi[last_doi:len(stringul_doi)]
            print(answ)
        elif min(len(zero_unu), len(zero_trei)) >= jumatate:
            answ = ''
            cate = min(len(zero_unu), len(zero_trei))
            last_unu = 0
            last_trei = 0
            for i in range(cate):
                answ += stringul_unu[last_unu:zero_unu[i]]
                answ += stringul_trei[last_trei:zero_trei[i]]
                last_unu = zero_unu[i] + 1
                last_trei = zero_trei[i] + 1
                answ += '0'
            answ += stringul_unu[last_unu:len(stringul_unu)]
            answ += stringul_trei[last_trei:len(stringul_trei)]
            print(answ)
        elif min(len(zero_doi), len(zero_trei)) >= jumatate:
            answ = ''
            cate = min(len(zero_doi), len(zero_trei))
            last_doi = 0
            last_trei = 0
            for i in range(cate):
                answ += stringul_doi[last_doi:zero_doi[i]]
                answ += stringul_trei[last_trei:zero_trei[i]]
                last_doi = zero_doi[i] + 1
                last_trei = zero_trei[i] + 1
                answ += '0'
            answ += stringul_doi[last_doi:len(stringul_doi)]
            answ += stringul_trei[last_trei:len(stringul_trei)]
            print(answ)
        elif min(len(unu_unu), len(unu_doi)) >= jumatate:
            answ = ''
            cate = min(len(unu_unu), len(unu_doi))
            last_unu = 0
            last_doi = 0
            for i in range(cate):
                answ += stringul_unu[last_unu:unu_unu[i]]
                answ += stringul_doi[last_doi:unu_doi[i]]
                last_unu = unu_unu[i] + 1
                last_doi = unu_doi[i] + 1
                answ += '1'
            answ += stringul_unu[last_unu:len(stringul_unu)]
            answ += stringul_doi[last_doi:len(stringul_doi)]
            print(answ)
        elif min(len(unu_unu), len(unu_trei)) >= jumatate:
            answ = ''
            cate = min(len(unu_unu), len(unu_trei))
            last_unu = 0
            last_trei = 0
            for i in range(cate):
                answ += stringul_unu[last_unu:unu_unu[i]]
                answ += stringul_trei[last_trei:unu_trei[i]]
                last_unu = unu_unu[i] + 1
                last_trei = unu_trei[i] + 1
                answ += '1'
            answ += stringul_unu[last_unu:len(stringul_unu)]
            answ += stringul_trei[last_trei:len(stringul_trei)]
            print(answ)
        elif min(len(unu_doi), len(unu_trei)) >= jumatate:
            answ = ''
            cate = min(len(unu_doi), len(unu_trei))
            last_doi = 0
            last_trei = 0
            for i in range(cate):
                answ += stringul_doi[last_doi:unu_doi[i]]
                answ += stringul_trei[last_trei:unu_trei[i]]
                last_doi = unu_doi[i] + 1
                last_trei = unu_trei[i] + 1
                answ += '1'
            answ += stringul_doi[last_doi:len(stringul_doi)]
            answ += stringul_trei[last_trei:len(stringul_trei)]
            print(answ)
main()

Solution (Python):
from sys import *
input = stdin.readline

def superstring(x, y, fx, n):
    ans = ''
    (i, j) = (0, 0)
    while i < 2 * n and j < 2 * n:
        if x[i] == y[j]:
            ans += x[i]
            i += 1
            j += 1
        elif x[i] != fx:
            ans += x[i]
            i += 1
        else:
            ans += y[j]
            j += 1
    return ans + x[i:] + y[j:]
for _ in range(int(input())):
    n = int(input())
    (a, b, c) = (input().strip(), input().strip(), input().strip())
    (one, zero) = ([], [])
    for i in [a, b, c]:
        if i.count('0') >= n:
            zero.append(i)
        else:
            one.append(i)
    currans = ''
    if len(zero) > len(one):
        currans = superstring(zero[0], zero[1], '0', n)
    else:
        currans = superstring(one[0], one[1], '1', n)
    print(currans.rjust(3 * n, '0'))

Solution (Python):
from typing import List
from collections import OrderedDict

def solve():
    n = int(input())
    a = input()
    b = input()
    c = input()
    index_a = 0
    index_b = 0
    index_c = 0
    res = ''
    while max(index_a, index_b, index_c) < 2 * n:
        if a[index_a] == b[index_b]:
            res += a[index_a]
            index_c += a[index_a] == c[index_c]
            index_a += 1
            index_b += 1
        elif a[index_a] == c[index_c]:
            res += a[index_a]
            index_b += a[index_a] == b[index_b]
            index_a += 1
            index_c += 1
        elif b[index_b] == c[index_c]:
            res += b[index_b]
            index_a += a[index_a] == b[index_b]
            index_b += 1
            index_c += 1
    d = [[index_a, a], [index_b, b], [index_c, c]]
    d.sort()
    res += d[1][1][d[1][0]:]
    print(res)

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()