It is only impossible if the number of k is 0 and r is not universal, or if r consists of only one distinct character.

Time complexity: $$$O(n)$$$

For the MEX to be 0, we must remove all 0s from the array and then apply the operation on the whole array. We can remove all zeroes in one operation (with endpoints on the leftmost and rightmost zeroes) unless both the first and last element are 0, in which case it takes two operations. Once all zeros are removed, we can MEX the whole array resulting in 0.

Time complexity: $$$O(n)$$$

It is always possible if x != y. WLOG, assume x>y. Note that a+b=a^b (^ is xor) if and only if the bitwise and of a and b is 0. Let M be the least power of 2 greater than or equal to x. Using k = M-x will set all bits in x+k to zero except one, and since x>y, the bitwise and of x+k and y+k will be 0.

Time complexity: $$$O(1)$$$ (with bitwise operations)

Consider reversing time: we iterate over the dishes backwards, and at each move we can increase r by one or take the current dish and decrease it by k. We must end with r >= 0. We greedily eat a dish every time we can. If we ate a dish earlier but the current dish has a greater value of d[i] than it, we can replace the older dish with the current one to maximize the answer (since we can save the k for the current dish instead of using it earlier). To do this, we maintain a sorted multiset of all dishes we have taken so far. The answer is simply the sum of all elements in the multiset.

Time complexity: $$$O(n\log{n})$$$

Let A be the sum of all elements in a and B be sum of all elements in B. Note that k must divide B-A. We can iterate over all divisors of this value and check each of them. This will run in time since the maximum number of divisors of B-A is less than 3000.

Time complexty: $$$O(3000n\log{n})$$$

Consider the middle index of the final subarray. We can iterate over this index, keeping track of the closest occurrences to the left and right for each index using sets. For each middle index, we iterate over all values 1 to k (except the value of the middle index) and choose the closest index (either to the left or right) to the middle index, or mark it as equal distance to both sides. If the number of values on both sides is equal (or differs by 1), we can update the answer with the number of required moves in this case.

Time complexity: $$$O(n^2)$$$