Author: | Anton Trygub and Alex Danilyuk |
As the problem is purely constructive and there are a lot of possible directions, we would not be surprised if there are solutions that are different from our solution in every regard. Having said that, we are not aware of any such solutions. There is no logical reasoning behind the general construction, we just tried a lot of things and stumbled on the one that works, although at least three people came up with this construction independently, so it doesn't seem like pure luck. Let's jump into the general construction.
S = 0^{k_1} \, 01 \, 0^{k_2} \, 01 \, \ldots \, 0^{k_t} \, 01,
T = (01)^{(n+t)},
where n, t, k_1, k_2, \ldots, k_t — some non-negative integers (there might be more concise constructions with the same idea, I personally find this one the clearest). We will also require k_1 + k_2 + \ldots + k_t \ge n.
I state that it is possible to take all from and all from , which means that length of LCS(S, T) = n + 2t, and the only possibility to reach this is to be of the form 0^{a_1} \, 01 \, 0^{a_2} \, 01 \, \ldots \, 0^{a_t} \, 01, where 0 \le a_i \le k_i, \sum_{i=1}^{t} a_i = n.
Now we want to choose n, t, k_1, k_2, \ldots, k_t such that the number of ways to choose a_1, a_2, \ldots, a_t is exactly .
Let's first understand what is the number of ways to choose a_1, a_2, \ldots, a_t for the given n, t, k_1, k_2, \ldots, k_t. It is a standard combinatorics problem:
If there were no limitations a_i \le k_i, the answer would be equal to \binom{n + t - 1}{t - 1}. Let's now apply inclusion-exclusion principle, fix the set of a_i > k_i (that is, the condition a_i \le k_i is violated). The answer will be equal to \sum_{I \in 2^{[1..t]}} (-1)^{|I|} \binom{n - \sum_{i \in I} (k_i + 1) + t - 1}{t-1}.
This doesn't look good, because we can control only t+2 parameters, while the number of summands is 2^{t}. Let's make most of them be equal to zeroes! Let's choose k_i close to , more formally, we want k_i + k_j \ge n, so that we can't violate two or more conditions at once. This way the answer will be \binom{n + t - 1}{t - 1} - \sum_{i=1}^{t} \binom{n - k_i - 1 + t - 1}{t - 1}.
With the answer in this form the idea for the construction is clear: fix , choose some such that \binom{n + t - 1}{t - 1} \ge K, represent \binom{n + t - 1}{t - 1} - K as the sum of binomial coefficients.
With t=3 we are dealing with triangular numbers, and there is actually a theorem that states that every number is representable by a sum of at most three triangular numbers. Unfortunately, t=3 means that we will need n \approx \sqrt{2K} to get big enough value, and we can't afford that.
t=4 would resolve this issue, we will be good with n \approx \sqrt[3]{6K}. Now we are dealing with tetrahedral numbers and... they are good enough. There is an unproven conjecture that says that every number is representable by a sum of at most five tetrahedral numbers. Fortunately for us, this conjecture is checked for all numbers up to 10^{10}, moreover, there are only (known) numbers that actually require five summands, the largest being . In case we are unfortunate to encounter such a test, we can just choose a larger .
The (almost) last issue is that we are not satisfied with just knowing that the representation in a form of such sum exists, we actually need to construct one. The largest value of we might want to use is less than , which means the numbers we want to represent in this form are bounded by \binom{1850}{2} + 343\,867 < 2\,100\,000. Thus we can use only the first tetrahedral numbers (as \binom{240}{3} > 2\,100\,000). We can implement DP in 240 \cdot 2\,100\,000 to construct the representation, and if for some reason it is slow, use bitsets to speed it up.
The actual last issue is that we have to ensure that k_i + k_j \ge n actually holds. It will be true automatically for large values of , because \binom{n - k_i - 1 + t - 1}{t - 1} \le 2 \binom{n + t - 1}{t - 2}, and that means that for large enough n - k_i < n / 2. You might need to use some simpler approach for small values of , for example, the solution above with t=2 or t=3 (t=2 should be enough).