Curse
Contest: Codeforces Round 1004 (Div. 1)
Difficulty rating: 3300
Tags: constructive algorithms, dp, math

You are given two arrays of integers: $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_m$$$.

You need to determine if it is possible to transform array $$$a$$$ into array $$$b$$$ using the following operation several (possibly, zero) times.

- Among all non-empty subarrays$$$^{\text{∗}}$$$ of $$$a$$$, choose any with the maximum sum, and replace this subarray with an arbitrary non-empty integer array.

If it is possible, you need to construct any possible sequence of operations. Constraint: in your answer, the sum of the lengths of the arrays used as replacements must not exceed $$$n + m$$$ across all operations. The numbers must not exceed $$$10^9$$$ in absolute value.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 200$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ ($$$1 \le n, m \le 500$$$) — the lengths of arrays $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$) — the elements of array $$$a$$$.

The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$-10^6 \le b_i \le 10^6$$$) — the elements of array $$$b$$$.

It is guaranteed that the sum of the values of $$$n$$$ across all test cases does not exceed $$$500$$$.

It is guaranteed that the sum of the values of $$$m$$$ across all test cases does not exceed $$$500$$$.

Output format:
For each test case, output $$$-1$$$ if it is impossible to transform array $$$a$$$ into array $$$b$$$.

Otherwise, in the first line, output the number of operations $$$0 \leq q \leq n + m$$$. Then output the operations in the following format in the order they are performed.

In the first line of each operation, print three numbers $$$l, r, k$$$ ($$$1 \leq l \leq r \leq |a|$$$). In the second line, print $$$k$$$ integers $$$c_1 \ldots c_k$$$, which means replacing the segment $$$a_l, \ldots, a_r$$$ with the array $$$c_1, \ldots, c_k$$$.

The sum of $$$k$$$ across all $$$q$$$ operations must not exceed $$$n + m$$$. Additionally, it must hold that $$$-10^9 \leq c_i \leq 10^9$$$.

You do not need to minimize the number of operations.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

Note:
In the first test, the initial array is modified as follows:

$$$$$$ [2, -3, 2, 0] \to [2, -3, -3] \to [-3, -3, -3] \to [-3, -7, -3] \to [-3, -7, 0] $$$$$$

You may choose to output empty lines or not. Empty lines in the example are added for convenience.

Example input:
3
4 3
2 -3 2 0
-3 -7 0
2 1
-2 -2
2
5 4
-5 9 -3 5 -9
-6 6 -1 -9

Example output:
4
3 4 1
-3 

1 1 1
-3 

2 2 1
-7 

3 3 1
0
 
-1

3
2 4 1
-5 

1 1 1
-6 

2 2 2
6 -1

Editorial:
$$$\operatorname{MSS}(a)$$$ — the maximum sum of a non-empty subarray $$$a$$$.
A detailed proof of the solution will be at the end of the analysis.
First, we need to characterize all arrays reachable from $$$a$$$ through operations. Often, in such cases, we want to find some property that remains unchanged during operations or changes in a predictable way (for example, only increases). However, in this problem, neither the elements nor the length of the array are constant, so at first glance, it is unclear what kind of invariant we want to find.
Let's consider a minimal example where not all arrays are explicitly reachable from the original one, and there are some restrictions. Let $$$a = [-1, -1]$$$. In the first operation, we replace one of the $$$-1$$$s. If we replace it with an array with a maximum subarray sum $$$> -1$$$, we are then obliged to replace something inside that subarray. If we replace it with an array with a maximum subarray sum $$$\leq -1$$$, we must also replace either strictly inside that array or the second $$$-1$$$. Thus, all changes occur either in the array generated by the first $$$-1$$$ or the second $$$-1$$$. We can represent a barrier between the elements of the array: $$$[(-1) \color{red}{|}(-1)]$$$. Any replacement of a subarray will never cross this barrier.
It turns out that, in general, we can set such barriers that will never be crossed during operations in a fairly intuitive way.
For the array $$$a_1, ..., a_n$$$, we define a cool partition of the array into subsegments recursively:
• The cool partition of an empty array is empty.
• We find any segment of maximum length $$$[l,r]$$$ such that $$$\operatorname{MSS}(a) = a_l + \ldots + a_r$$$. Then the cool partition will consist of the segments of the cool partition $$$a_1, \ldots, a_{l-1}$$$, the segment $$$[l,r]$$$, and the segments of the cool partition $$$a_{r+1}, \ldots, a_n$$$.
It is not difficult to prove that the cool partition is uniquely defined for each array. It turns out that if we represent barriers between neighboring segments of the cool partition, these barriers will never be crossed during operations. Moreover, the cool partition of any array obtained from $$$a$$$ through operations will contain at least the same barriers as $$$a$$$.
At the same time, due to the properties of construction, one operation in the array $$$a$$$ completely replaces one of the segments of the cool partition with the maximum sum. It turns out that all arrays reachable from $$$a$$$ must have the following structure:
• Any number $$$x$$$ is chosen from the sums of the segments of the cool partition of $$$a$$$.
• Among the segments of the cool partition of $$$a$$$, those segments whose sum is $$$< x$$$ remain unchanged.
• Among the remaining segments: one is replaced with an arbitrary non-empty array, and all others with an arbitrary non-empty array $$$y$$$ such that $$$\operatorname{MSS}(y) \leq x$$$.
The sequence of operations is as follows: we replace all segments in descending order of their sums. The segment we want to replace with an arbitrary array is first replaced with $$$\{x\}$$$. After all segments are replaced, the last operation replaces this $$$\{x\}$$$ with an arbitrary array.
Knowing this, we can solve the problem using dynamic programming in $$$O(n^2 \cdot m)$$$.
We will precompute the cool partition of the array $$$a$$$. Then we can iterate over the separator value $$$x$$$ in $$$O(n)$$$, and for each such value, we will run the dynamic programming $$$dp[i][j][flag]$$$ — whether it is possible to match a prefix of the first $$$i$$$ segments of the special partition to the prefix $$$b_1,b_2,\ldots,b_j$$$, where $$$flag$$$ indicates whether we have already used a replacement with an arbitrary non-empty array, or all current replacements were with arrays with $$$\operatorname{MSS} \leq x$$$. Naively, the recalculation will work in $$$O(n)$$$, but with some simple optimizations, it is easy to achieve a total asymptotic complexity of recalculation for all states of $$$O(n \cdot m)$$$, and then the entire dynamic programming will work in $$$O(n \cdot m)$$$, and the whole solution in $$$O(n^2 \cdot m)$$$.
Now, here is the complete proof of the solution.
Statement
Given an array $$$a_1, a_2, \ldots, a_n$$$ of integers.
The following operation is given:
• Choose any pair $$$(l, r)$$$ such that $$$1 \leq l \leq r \leq n$$$, and $$$a_l + \ldots + a_r$$$ is maximum among all numbers of the form $$$a_{l'} + \ldots + a_{r'}$$$.
• Replace the subarray $$$a_l...a_r$$$ with an arbitrary non-empty array. That is, replace the working array $$$[a_1, \ldots, a_n]$$$ with $$$[a_1, \ldots, a_{l-1}, b_1, \ldots, b_m, a_{r+1}, \ldots, a_n]$$$, where $$$m \geq 1$$$ and $$$b_1, ..., b_m$$$ are chosen by you, and the numbers are integers.
Goal: characterize all arrays reachable from $$$[a_1, \ldots, a_n]$$$ through unlimited applications of such operations.
General Remarks
$$$[l, r]$$$ denotes the subarray $$$a_l...a_r$$$. $$$(l \leq r)$$$
$$$sum(l, r)$$$ denotes $$$a_l + \ldots + a_r$$$.
Definition 1
A segment $$$[l, r]$$$ will be called cool if:
• $$$sum(l, r)$$$ is maximum among all segments.
• $$$\forall (l_0 \leq l) \wedge (r_0 \geq r) \wedge (l_0 < l \vee r_0 > r)$$$ it holds that $$$sum(l_0, r_0) < sum(l, r)$$$.
Claim 2
If operations are applied only to cool segments, the set of reachable arrays will not change.
Proof:
If the segment $$$[l, r]$$$ is not cool, then $$$\exists l_0, r_0$$$ such that $$$l_0 \leq l, r_0 \geq r$$$ and $$$[l_0, r_0]$$$ is cool. Then applying the operation to $$$[l, r]$$$ with the array $$$b_1, .., b_m$$$ can be replaced by applying the operation to $$$[l_0, r_0]$$$ with the array $$$a_{l_0}, \ldots, a_{l-1}, b_1, \ldots, b_m, a_{r+1}, \ldots, a_{r_0}$$$, and the array after replacement will remain the same.
Therefore, any operation with a non-cool segment can be freely replaced with an operation with a cool one, which proves the claim.
From now on, we will assume that operations are applied only to cool segments. Thanks to Claim 2, we know that this is equivalent to the original problem.
Claim 3
Two different cool segments do not intersect. That is, if $$$[l_1,r_1]$$$ and $$$[l_2,r_2]$$$ are cool segments, and $$$l_1 \neq l_2 \vee r_1 \neq r_2$$$, it follows that $$$[l_1,r_1] \cap [l_2,r_2] = \emptyset$$$.
Proof:
Assume that there are intersecting cool segments. We will consider two cases: intersection and nesting.
1. We can consider the union and intersection of our segments. The sum of the union and intersection then equals the sums of our cool segments. Thus, either the sum of the union is not less, and the segments are not cool, since they can be expanded. Or the sum of the intersection is greater, and the segments are not cool, since there exists one with a greater sum.
2. Nesting is impossible, as the smaller segment could then be expanded to a larger one, meaning by definition it is not cool.
Let's introduce the concept of partitioning the array into cool segments: a cool partition.
Definition 4
For the array $$$a_1, ..., a_n$$$, we define a cool partition recursively:
• If $$$[1,n]$$$ is a cool segment, then the cool partition will consist of one segment $$$[1,n]$$$.
• Otherwise, we find any cool segment $$$[l,r]$$$. Then the cool partition will consist of the segments of the cool partition $$$a_1, \ldots, a_{l-1}$$$, the segment $$$[l,r]$$$, and the segments of the cool partition $$$a_{r+1}, \ldots, a_n$$$.
It is easy to see that the cool partition is uniquely defined. This follows from Claim 3.
Claim 5
In one operation, one of the segments of the cool partition with the maximum sum is completely replaced.
It is obvious that we literally defined the cool partition such that all cool segments of the original array are included, and we replace only cool segments.
Claim 6
The existing boundaries of the cool partition will necessarily remain the same after the operation.
That is, if our array and its cool partition are: $$$[a_1, \ldots, a_{r_1}], [a_{r_1+1}, \ldots, a_{r_2}], \ldots, [a_{r_{k-1}+1}, \ldots, a_{r_k}]$$$
And we replace the cool segment $$$[a_{r_i+1}, \ldots, a_{r_{i+1}}]$$$ with maximum sum with some $$$b_1,\ldots, b_m$$$, then after the operation, the cool partition of the array will continue to contain all the same segments to the left and right of the replaced one. That is, the cool partition of the new array will look like: $$$[a_1, \ldots, a_{r_1}], [a_{r_{i-1}+1}, \ldots, a_{r_i}], BCOOL, [a_{r_{i+1}+1}, \ldots, a_{r_{i+2}}], \ldots, [a_{r_{k-1}+1}, \ldots, a_{r_k}]$$$
Where $$$BCOOL$$$ is the cool partition of the array $$$b_1,\ldots, b_m$$$.
Proof:
Any subarray $$$M$$$ from the cool partition has the property that all sums of subarrays of $$$M$$$ do not exceed the sum of $$$M$$$. Otherwise, a subsegment $$$M$$$ with a greater sum would have been chosen instead of $$$M$$$ in the cool partition.
Also, we note that $$$\forall l \leq r_i a_l+\ldots+a_{r_i}<0$$$, since otherwise $$$[a_{r_i+1}, \ldots, a_{r_{i+1}}]$$$ would not be a cool segment, as it could be expanded to the left without losing its sum. Similarly, it follows that $$$\forall R \geq r_{i+1}+1, a_{r_{i+1}+1} + \ldots + a_R < 0$$$.
Therefore, the boundaries around the old cool segment will necessarily be preserved. If any of them is violated, the intersecting boundary array will have a prefix or suffix with a negative sum, which violates the property of the subarray from the cool partition, as the complement of this prefix/suffix would have a greater sum than the subarray itself.
Since the boundaries hold, the cool partition in 3 parts will be independent of each other, and thus it will remain the same on the left and right as before, while inside will be $$$BCOOL$$$.
Definition 7
The scale of the operation replacing the segment $$$[l,r]$$$ will be called $$$sum(l,r)$$$.
Definition 8
A finite sequence of operations $$$op_1, op_2, \ldots, op_k$$$ will be called reasonable if the sequence of scales of the operations is strictly non-increasing. That is, $$$s_i \geq s_{i+1}$$$ for all $$$i$$$, where $$$s_i$$$ is the scale of the $$$i$$$-th operation.
Claim 9
If we consider only reasonable sequences of operations, the set of reachable arrays will remain the same.
If there is some unreasonable sequence of operations, then it has $$$s_i < s_{i+1}$$$.
This means that during the $$$i$$$-th operation, the maximum sum of the cool segment increased. But as we know, the old segments all remained, and only $$$BCOOL$$$ is new. Thus, the next operation will be entirely within $$$b_1,\ldots,b_m$$$. But then we could have made this replacement in the previous operation immediately, resulting in one less operation.
Therefore, the shortest path to each reachable array is reasonable, as any unreasonable one can be shortened by one operation. Thus, any reachable array is necessarily reachable by reasonable sequences of operations.
From now on, we will consider only reasonable sequences of operations. Thanks to Claim 9, this is equivalent to the original problem.
Now we are ready to formulate and prove the necessary condition for a reachable array.
Let the sums in the segments of the cool partition of the original array be: $$$[s_1, s_2, \ldots, s_k]$$$.
It is claimed that all reachable arrays must have the following form (necessary condition):
1. Some integer $$$x$$$ is chosen.
2. Among the segments of the cool partition, those segments whose sum is $$$<x$$$ remain unchanged.
3. Among the remaining segments: one chosen segment is replaced with an arbitrary non-empty array, and all others with an arbitrary non-empty array such that the sum of its maximum subarray $$$\leq x$$$.
And the reachable array = concatenation of these segments.
Let's show that any finite reasonable sequence of operations must lead us to an array of the described form.
We have the initial boundaries of the cool partition of the given array. As we know, they will remain with us forever. Also, the sums in these segments cannot increase BEFORE the last operation is applied, as we are only considering reasonable sequences. The very last operation can, of course, increase the sum.
Therefore, let us say that in the last operation we replace the subarray with scale $$$=x$$$.
We look at the state of our array before this last operation.
The segments of the cool partition with a sum $$$<x$$$ could not have changed, again because we are only considering reasonable sequences, and since $$$x$$$ is the scale of the last operation, ALL operations had a scale of at least $$$x$$$.
In the segments of the cool partition with a sum $$$\geq x$$$, now between these same boundaries, the sum of the maximum subarray must be $$$\leq x$$$. New boundaries of the cool partition may have appeared, but this is not important to us. We are only looking at the original boundaries and the sums between them.
Thus, it turns out to be a description as above. And in the last operation, one of the segments is replaced with an arbitrary array. This last segment must also lie entirely within the boundaries of one of the segments of the original cool partition. Therefore, we can safely say that the entire corresponding cool segment was replaced, as in the claimed description.
In the end, any sequence of operations must fit the description.
And it remains to show the sufficiency: that any array from the description is reachable.
We simply take and replace the cool segments with the desired arrays in descending order of their sums. The one we plan to replace last, with an arbitrary array, is first replaced simply with $$$[x]$$$, and then when we replace everything we wanted, we replace it last with an arbitrary array.
Thus, the proposed description is indeed the description of all reachable arrays.