This problem is solvable for all cases except 4 × 4.

The important thing in the problem is to notice that there exists a structure that allows us to visit every cell of a 3 × 4 (or 4 × 3) rectangle and finish in a cell that is opposite to the starting cell. This can be seen in the following image, which is a solution for the 4 × 6 case:

And as can be seen in a solution of a 6 × 6 grid, this structure can be made higher:

And they can be put next to each other:

So now we can solve cases where n ≡ 2 (mod 4) or m ≡ 2 (mod 4). We still need a solution for the case n ≡ 0 (mod 4) or m ≡ 0 (mod 4). This can be solved by using the same structure as before, but this time making it wider and reducing this back to m ≡ 2 (mod 4) case:

And now we can combine all this into a 100p solution.

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.