Binary Path
Contest: Codeforces Round 930 (Div. 2)
Difficulty rating: 1300
Tags: dp, greedy, implementation

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:

1. Find the lexicographically smallest$$$^\dagger$$$ string you can attain by choosing any available path;
2. 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 format:
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 format:
For each test case, output two lines:

1. The lexicographically smallest string you can attain by choosing any available path;
2. The number of paths that yield this string.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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:

Example input:
3
2
00
00
4
1101
1100
8
00100111
11101101

Example output:
000
2
11000
1
001001101
4

Editorial:
Let the string achieved by moving down on the $$$i$$$-th column be $$$S_i$$$. Then, for any $$$1 \le k < n$$$, one can observe that $$$S_k$$$ and $$$S_{k+1}$$$ can only differ by at most one index, which is index $$$k+1$$$. Thus, comparing $$$S_k$$$ and $$$S_{k+1}$$$ lexicographically can be done in $$$\mathcal{O}(1)$$$, by comparing this one index.
After finding the lexicographically smallest string, counting the occurrence of this string can be done straightforwardly in $$$\mathcal{O}(n)$$$.
The implementation can differ for each participant, but the following method provides a clean implementation. Let the initial coordinate be $$$(1,1)$$$, and maintain a counter which is initially reset to $$$1$$$. Then repeat the following until we reach $$$(2,n)$$$.
1. If we are on row $$$2$$$, move to the right;
2. If we are on column $$$n$$$, move downwards;
3. From here, let the character on the right be $$$a$$$, and one below be $$$b$$$.
4. If $$$a>b$$$, move downwards;
5. If $$$a<b$$$, move to the right and reset the counter to $$$1$$$;
6. If $$$a=b$$$, move to the right and increment the counter.
In the end, the string on the path we passed through will be lexicographically smallest, and the integer on the counter will be the number of occurrences.