I solved the problem by going through all the possible solutions (taking the best one of course) and using pretty simple observations:

• Between every "print" command we will use at most 1 "multiply" command and 1 "add" command (any sequence with more commands can be compressed to at most 1 multiply and then at most 1 add).
• At any time (after a print) we will have a set of current numbers, on which we will perform a multiplication and an addition to reach a new value, which will be a prefix of the remainder of the corresponding number. If we denote the currect value as A and the wanted value as B, then all the ways to multiply and then add to get from A to B are on the line f(X) = B - A * X: for any point on that line with coordinates (x₁, y₁) we can take A, multiply it by x₁ and add to it y₁. Of course, we will only look at the non-negative integer coordinates.

With this, if we have 2 lines that represent 2 solutions, then the only possible way to multiply and add will correspond to their intersection (which might not have nonnegative integer coordinates, in which case there is no answer). For example if I want to get from 2 to 5 and from 4 to 9 at the same time, then I can form the lines  - 2x + 5 and  - 4x + 9. They intersect at (2, 1), which means I can multiply by 2 and add 1.

Here is what I did: at any call of the recursion, I maintain the last value I printed for each string as its substring inside that string. From here I have 2 cases:

• All the previously printed substrings are the same. In this case I need to make sure the remainder of each string is identical and if that's the case, then I can solve for all of the strings as if I'm solving for 1 of them, which is simple.
• There exists a pair of different previously printed substrings. I can find this pair (in , I just find the first one that's different from the first substring). The reason I want such pair is because their corresponding lines will have different slopes, which means I won't have to deal with no intersection/identical lines.

With these two, I go over all possibilities to print the next substring in their strings. For every such pair I find the intersection of those lines, and if their intersection leads to some valid pair (x₁, y₁), then I go over all strings, apply this transformation on all their previously printed substrings and check whether the result is a prefix of the remaining string I need to print. If this is true for all strings (which is a rare case), then I can continue the recursion with these operations being applied.

With every call I also maintain the steps I performed. The cases that end the recursion are if I finished all strings (which means it's a valid answer), if I finished only some of the strings (which means it's an invalid answer).

There's also something to be aware of: if in some string, the next character I need to print is 0, then the operation that must be applied is "multiply 0".

Unfortunately, I don't know the complexity of this solution, but on all cases it wrote that I took 0.000s.

First off we sort the values in the array. Now every set of values we pick will be contiguous, because if we pick a start value and an end value then we can take any value between them and the answer won't increase.

Let's binary search on the answer, on the current iteration we're checking whether we can solve the problem with the answer being  ≤ X. Let DP_i be 1 if we can split the first i values to valid groups such that the answer does not exceed X.

Notice that with the current X, we can compute for each value in the array the leftmost value such that their difference does not exceed X (which means, we can find the largest segment we can take which ends on that value). We can compute this in amortized using 2 pointers. This segment will also have a lowerbound of a and an upperbound of b over its length. For an index k, we will denote the leftmost index and the rightmost index on which that segment can start at, as l_k and r_k respectively.

Now we have a formula for DP_k: it is equal to 1 if and only if there exists such an l_k ≤ m ≤ r_k that DP_m - 1 = 1. In order to be able to solve such queries we will maintain the prefix sum of array DP, then we can query for a range sum in and update the current cell using the previous one. Because of the binary search, the total time complexity is .

There's the special case n = 1, which needs to be solved separately.

Solution for n > 1:

Let's denote length of a string s by |s| and its substring from a-th character to b-1-th character by s[a..b].

We solve the problem by using recursion. For each substring of b[0][0..i] and b[1][0..j], where 1 ≤ i ≤ |b[0]| and 1 ≤ j ≤ |b[1]|, check if it's possible to find non-negative integers x and y such that a[0]·x + y = b[0][0..i] and a[1]·x + y = b[1][0..j]. If such integers x and y exist, then check if a[k]·x + y is a substring of b[k] for every k.

If that's true for every value of k, then multiply each a[k] by x and add y to it, and erase that substring from b[k]. Keep doing this until either all b's are empty or the previously mentioned condition is false. If all strings are empty, you have found one solution, even though it's not necessarily the shortest one.

Use binary search and two pointers technique to solve the problem in .

Sort the given array v, and binary search for the answer k.

When checking the condition for binary search, first calculate for each i a value t[i], which is the furthest index j such that j - i < b and |v[i] - v[j]| ≤ k.

For the array v = [1, 1, 1, 5, 8, 8, 8, 10] and a = 3, b = 5 the array t would be [3, 3, 3, 6, 7, 7, 7, 7].

Now notice that if |i - t[i]| - 1  ≥ a, then you can select a subarray from i to [i + a - 1, t[i]] ie. you can "jump" from i to range [i + a, t[i] + 1]. Because array t is increasing, then both i + a and t[i] + 1 are increasing too.

We start with a queue q that contains a range $[0, 0]$, and at each i we check if there's any range [l, r] such that l ≤ i ≤ r. If there isn't any, then there's no solution for k. Otherwise we push the range [i + a, t[i]  + 1] to the queue.

My 80 points solution:

Let o = [1..n].

Repeat the following process several times:

Random shuffle o. Then start doing depth first searches starting from each o[i] for every i in 0..n - 1. Every time you encounter a cycle, evacuate the node where you found this cycle. When there are no cycles you can successfully evacuate all other houses.

Because the test cases give you the number of the test case, you can try different seeds for the random number generator and find a good seed for each case.