Boboniu and String
Contest: Codeforces Round 664 (Div. 1)
Difficulty rating: 2600
Tags: binary search, geometry, ternary search

Boboniu defines BN-string as a string $$$s$$$ of characters 'B' and 'N'.

You can perform the following operations on the BN-string $$$s$$$:

- Remove a character of $$$s$$$.
- Remove a substring "BN" or "NB" of $$$s$$$.
- Add a character 'B' or 'N' to the end of $$$s$$$.
- Add a string "BN" or "NB" to the end of $$$s$$$.

Note that a string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Boboniu thinks that BN-strings $$$s$$$ and $$$t$$$ are similar if and only if:

- $$$|s|=|t|$$$.
- There exists a permutation $$$p_1, p_2, \ldots, p_{|s|}$$$ such that for all $$$i$$$ ($$$1\le i\le |s|$$$), $$$s_{p_i}=t_i$$$.

Boboniu also defines $$$\text{dist}(s,t)$$$, the distance between $$$s$$$ and $$$t$$$, as the minimum number of operations that makes $$$s$$$ similar to $$$t$$$.

Now Boboniu gives you $$$n$$$ non-empty BN-strings $$$s_1,s_2,\ldots, s_n$$$ and asks you to find a non-empty BN-string $$$t$$$ such that the maximum distance to string $$$s$$$ is minimized, i.e. you need to minimize $$$\max_{i=1}^n \text{dist}(s_i,t)$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$).

Each of the next $$$n$$$ lines contains a string $$$s_i$$$ ($$$1\le |s_i| \le 5\cdot 10^5$$$). It is guaranteed that $$$s_i$$$ only contains 'B' and 'N'. The sum of $$$|s_i|$$$ does not exceed $$$5\cdot 10^5$$$.

Output format:
In the first line, print the minimum $$$\max_{i=1}^n \text{dist}(s_i,t)$$$.

In the second line, print the suitable $$$t$$$.

If there are several possible $$$t$$$'s, you can print any.

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

Note:
In the first example $$$\text{dist(B,BN)}=\text{dist(N,BN)}=1$$$, $$$\text{dist(BN,BN)}=0$$$. So the maximum distance is $$$1$$$.

Example input:
3
B
N
BN

Example output:
1
BN

Example input:
10
N
BBBBBB
BNNNBBNBB
NNNNBNBNNBNNNBBN
NBNBN
NNNNNN
BNBNBNBBBBNNNNBBBBNNBBNBNBBNBBBBBBBB
NNNNBN
NBBBBBBBB
NNNNNN

Example output:
12
BBBBBBBBBBBBNNNNNNNNNNNN

Editorial:
It's obvious that the operation of BN-string is equivalent to the operation of BN-set, which I'm talking about, for a multi set $$$s$$$ contains only B and N:
• Remove a B or an N (if exists) from $$$s$$$.
• Insert a B or an N into $$$s$$$.
• Remove a B and an N from $$$s$$$.
• Insert a B and an N into $$$s$$$.
So let's use pair $$$(x,y)$$$ to denote a BN-set, which means there are $$$x$$$ B and $$$y$$$ N in it. We can do an operation to move to $$$(x,y\pm 1),(x\pm 1,y),(x\pm 1,y\pm 1)$$$.
The definition of similar of BN-set $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is simply $$$x_1=x_2$$$ and $$$y_1=y_2$$$.
Now the problem is to find a $$$(x_t,y_t)$$$ and minimize $$$\max_{i=1}^n\text{dist}(s_i,t)$$$. There are many algorithms to solve it and I'll describe two of them.
We can figure out the distance between $$$s_1=(x_1,y_1)$$$ and $$$s_2=(x_2,y_2)$$$ is: $$$$$$ \text{dist}(s_1,s_2)=\begin{cases} |x_1-x_2|+|y_1-y_2| & (x_1-x_2)(y_1-y_2)<0\\ \max(|x_1-x_2|,|y_1-y_2|) & (x_1-x_2)(y_1-y_2) \ge 0 \end{cases} $$$$$$ It can be shown that the answer is a unimodal function on $$$xOy$$$. So by using Hill Climbing Algorithm, we can solve the problem in $$$O(nT)$$$, where $$$T$$$ denotes the times of iteration.
We also have non randomized algorithm. It can be shown that for a fixed pair $$$P=(p_x,p_y)$$$, all the pair with distance $$$x$$$ from $$$P$$$ forms a hexagon:
So if we draw a hexagon centered on $$$(x_t,y_t)$$$ with radius $$$\max_{i=1}^n\text{dist}(s_i,t)$$$, then it must cover all $$$s_i$$$.
So we can try to find a hexagon with minimal radius $$$r$$$ to cover all $$$s_i$$$ and then we can easily calculate $$$(x_t,y_t)$$$. Let's use binary search and do some condition tests to calculate $$$r$$$. The total time complexity is $$$O(n\log_2n)$$$.