Binary Path (Codeforces 1937B)
Tags: Greedy, dp

You are given a $$$2 \times n$$$ grid filled with zeros and ones. Let the number at the intersection of the $$$i$$$-th row and the $$$j$$$-th column be $$$a_{ij}$$$.There is a grasshopper at the top-left cell $$$(1, 1)$$$ that can only jump one cell right or downwards. It wants to reach the bottom-right cell $$$(2, n)$$$. Consider the binary string of length $$$n+1$$$ consisting of numbers written in cells of the path without changing their order.Your goal is to:   Find the lexicographically smallest$$$^\dagger$$$ string you can attain by choosing any available path;  Find the number of paths that yield this lexicographically smallest string. $$$^\dagger$$$ If two strings $$$s$$$ and $$$t$$$ have the same length, then $$$s$$$ is lexicographically smaller than $$$t$$$ if and only if in the first position where $$$s$$$ and $$$t$$$ differ, the string $$$s$$$ has a smaller element than the corresponding element in $$$t$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).The second line of each test case contains a binary string $$$a_{11} a_{12} \ldots a_{1n}$$$ ($$$a_{1i}$$$ is either $$$0$$$ or $$$1$$$).The third line of each test case contains a binary string $$$a_{21} a_{22} \ldots a_{2n}$$$ ($$$a_{2i}$$$ is either $$$0$$$ or $$$1$$$).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 two lines:   The lexicographically smallest string you can attain by choosing any available path;  The number of paths that yield this string. 

Note: In the first test case, the lexicographically smallest string is $$$\mathtt{000}$$$. There are two paths that yield this string:  In the second test case, the lexicographically smallest string is $$$\mathtt{11000}$$$. There is only one path that yields this string:  

Sample Inputs:
3
2
00
00
4
1101
1100
8
00100111
11101101

Sample Outputs:
000
2
11000
1
001001101
4

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

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

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

def readInt():
    return int(input())

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

def readStr():
    return input().strip()

def solve():
    (n, s, t) = (readInt(), readStr(), readStr())
    cnt = 0
    for i in range(n - 1):
        if s[i + 1] == t[i]:
            cnt += 1
        elif s[i + 1] == '1' and t[i] == '0':
            print(''.join(s[:i + 1]) + ''.join(t[i:]))
            print(cnt + 1)
            return
        else:
            cnt = 0
    print(''.join(s) + t[-1])
    print(cnt + 1)
    return
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    arr1 = input().strip()
    arr2 = input().strip()
    up_pos = -1
    lst_p = -1
    for i in range(n - 1):
        if arr1[i + 1] != arr2[i]:
            if arr1[i + 1] > arr2[i] and up_pos == -1:
                up_pos = i
                break
            lst_p = i
    if up_pos == -1:
        if lst_p == -1:
            print(arr1 + arr2[-1])
            print(n)
        else:
            print(arr1 + arr2[-1])
            print(n - lst_p - 1)
    else:
        print(arr1[:up_pos + 1] + arr2[up_pos:])
        print(up_pos - lst_p)

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

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 = inp()
    A1 = insr()
    A2 = insr()
    smallest = [A1[0]] + A2
    count = 1
    for i in range(1, n):
        if A1[i] < smallest[i]:
            smallest[i] = A1[i]
            count = 1
        elif A1[i] == smallest[i]:
            count += 1
        else:
            break
    print(''.join(smallest))
    print(count)
if __name__ == '__main__':
    t = inp()
    for i in range(t):
        solve()