There will be a scoreboard after the second day of the competition.

I can proudly say that I am the author of this problem :) This is the hardest and (IMHO) coolest problem in the problemset.

We will try to post the contest editorial in a few days. Meanwhile, I can give you several observations that might help :

We can check the case where the resulting A and B is the exactly same sequence quite easily. For the case where the resulting A and B is not the same :

1. There exists an optimal solution which only uses the type-3 operation once.
2. Suppose cntA is the number of operations (only consider type-1 operation) needed to make the sequence A arithmetic and cntB is the number of operations (only consider type-2 operation) needed to make the sequence B arithmetic. Then the answer is either cntA + cntB — 1 or cntA + cntB.

Dynamic programming.

First assume that in our solution string there will be no intersection of prefix s and suffix t. We can use the following state:

dp_t(i, j, k) means that there is a way to visit some cells from (i, j) such that the resulting string is t_k, t_k + 1, t_k + 2, ..., t_lt (where l_t is the length of t). We can do a similar thing for dp_s, but we should reverse s first.

This means that we can find two cells (i, j) and (i', j') where dp_s(i, j, 1) and dp_t(i', j', 1) are true. Then a valid solution is "start somewhere and end in (i, j), go to (i', j'), and end somewhere" and this string will contains s as a prefix and t as a suffix.

We can compute dp_s(i, j, k) and dp_t(i, j, k) in O(nm(l_s + l_t)); details are not very complicated, for example here is recurrence for t (g_i, j is the cell at (i, j)):

So, now all we have to do is "link" two cells where dp_s(i, j, 1) and dp_t(i', j', 1) are true using the minimum number of cells. So we should find the "closest pair of cells" (i, j) and (i', j') (i.e. where |i - i'| + |j - j'| are minimum) where dp_s(i, j, 1) and dp_t(i', j', 1) are true. We can do this using some sort of binary search in ; basically, list down all the values of (i, j) where dp_s(i, j, 1) is true and then binary search, for each i, the closest j to (i', j') for all (i', j') where dp_t(i', j', 1) is true. Probably there are some better ways to do it but this is the easiest. Take the one with the smallest |i - i'| + |j - j'|, say a, then the answer is (a - 1) + l_s + l_t (l_s is length of s, l_t is length of t).

Now, what happens if our answer has prefix s and suffix t overlapping? Then we will miss the optimal answer. You can see it by testing this solution on the test case given in subtask 2; the optimal answer is but this solution will give .

The remedy to this is surprisingly simple. Look for all u such that s_{l - u - 1}, s_l - u, s_{l - u + 1}, ..., s_l and t₁, t₂, t₃, ..., t_u are equal. You can do it in O(l_s²), no need for any fancy algorithms 'cause l_s is very small. This lets us find all the "cutting points" where s will overlap t in our solution.

Now we simply look for all pairs (i, j) where dp_s(i, j, 1) is true and check if dp_t(i, j, u + 1) is also true (basically skipping t₁, t₂, t₃, ..., t_u, since they are already covered by s) for some cutting point u (just check all up to l_s cutting points). You can then recover the answer in this case in O(nml_s).

In total, it runs in and it passes all subtasks.