Game With Triangles
Contest: Codeforces Round 1000 (Div. 2)
Difficulty rating: 2000
Tags: binary search, brute force, data structures, geometry, greedy, implementation, math, ternary search, two pointers

Even Little John needs money to buy a house. But he recently lost his job; how will he earn money now? Of course, by playing a game that gives him money as a reward! Oh well, maybe not those kinds of games you are thinking about.

There are $$$n+m$$$ distinct points $$$(a_1,0), (a_2,0), \ldots, (a_{n},0), (b_1,2), (b_2,2), \ldots, (b_{m},2)$$$ on the plane. Initially, your score is $$$0$$$. To increase your score, you can perform the following operation:

- Choose three distinct points which are not collinear;
- Increase your score by the area of the triangle formed by these three points;
- Then, erase the three points from the plane.

An instance of the game, where the operation is performed twice.

Let $$$k_{\max}$$$ be the maximum number of operations that can be performed. For example, if it is impossible to perform any operation, $$$k_\max$$$ is $$$0$$$. Additionally, define $$$f(k)$$$ as the maximum possible score achievable by performing the operation exactly $$$k$$$ times. Here, $$$f(k)$$$ is defined for all integers $$$k$$$ such that $$$0 \le k \le k_{\max}$$$.

Find the value of $$$k_{\max}$$$, and find the values of $$$f(x)$$$ for all integers $$$x=1,2,\ldots,k_{\max}$$$ independently.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le {3 \cdot 10^4}$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ pairwise distinct integers $$$a_1,a_2,\ldots,a_{n}$$$ — the points on $$$y=0$$$ ($$$-10^9 \le a_i \le 10^9$$$).

The third line of each test case contains $$$m$$$ pairwise distinct integers $$$b_1,b_2,\ldots,b_{m}$$$ — the points on $$$y=2$$$ ($$$-10^9 \le b_i \le 10^9$$$).

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, given that the maximum number of operations is $$$k_{\max}$$$, you must output at most two lines:

- The first line contains the value of $$$k_{\max}$$$;
- The second line contains $$$k_{\max}$$$ integers denoting $$$f(1),f(2),\ldots,f(k_{\max})$$$. You are allowed to omit this line if $$$k_{\max}$$$ is $$$0$$$.

Note that under the constraints of this problem, it can be shown that all values of $$$f(x)$$$ are integers no greater than $$$10^{16}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
On the first test case, there are $$$1+3=4$$$ points $$$(0,0),(0,2),(1,2),(-1,2)$$$.

It can be shown that you cannot perform two or more operations. The value of $$$k_{\max}$$$ is $$$1$$$, and you are only asked for the value of $$$f(1)$$$.

You can choose $$$(0,0)$$$, $$$(-1,2)$$$, and $$$(1,2)$$$ as the three vertices of the triangle. After that, your score is increased by the area of the triangle, which is $$$2$$$. Then, the three points are erased from the plane. It can be shown that the maximum value of your score after performing one operation is $$$2$$$. Therefore, the value of $$$f(1)$$$ is $$$2$$$.

On the fifth test case, there are $$$8+2=10$$$ points.

It can be shown that you cannot perform three or more operations. The value of $$$k_{\max}$$$ is $$$2$$$, and you are asked for the values $$$f(1)$$$ and $$$f(2)$$$.

To maximize the score with only one operation, you can choose three points $$$(198\,872\,582,0)$$$, $$$(-1\,000\,000\,000,2)$$$, and $$$(1\,000\,000\,000,2)$$$. Then, the three points are erased from the plane. It can be shown that the maximum value of your score after performing one operation is $$$2\,000\,000\,000$$$. Therefore, the value of $$$f(1)$$$ is $$$2\,000\,000\,000$$$.

To maximize the score with exactly two operations, you can choose the following sequence of operations.

- Choose three points $$$(-509\,489\,796,0)$$$, $$$(553\,177\,666,0)$$$, and $$$(-1\,000\,000\,000,2)$$$. The three points are erased.
- Choose three points $$$(-400\,714\,529,0)$$$, $$$(564\,040\,265,0)$$$, and $$$(1\,000\,000\,000,2)$$$. The three points are erased.

Then, the score after two operations becomes $$$2\,027\,422\,256$$$. It can be shown that the maximum value of your score after performing exactly two operations is $$$2\,027\,422\,256$$$. Therefore, the value of $$$f(2)$$$ is $$$2\,027\,422\,256$$$.

Example input:
5
1 3
0
0 1 -1
2 4
0 100
-100 -50 0 50
2 4
0 1000
-100 -50 0 50
6 6
20 1 27 100 43 42
100 84 1 24 22 77
8 2
564040265 -509489796 469913620 198872582 -400714529 553177666 131159391 -20796763
-1000000000 1000000000

Example output:
1
2
2
150 200
2
1000 200
4
99 198 260 283
2
2000000000 2027422256

Editorial:
Whenever the operation is performed, your score increases by $$$a_j-a_i$$$ or $$$b_j-b_i$$$, where $$$i$$$, $$$j$$$ are the indices you choose two points on (WLOG $$$a_i<a_j$$$ or $$$b_i<b_j$$$, but this assumption is not necessary). For simplicity, we will call an operation where you choose two on $$$y=0$$$ "Operation A", and those where you choose two on $$$y=2$$$ "Operation B".
Let us define a function $$$g(p,q)$$$ as the maximum score after performing "Operation A" $$$x$$$ times and "Operation B" $$$y$$$ times, assuming it is possible. Then, it is not hard to prove that $$$g(p,q)$$$ equates to the following value:
$$$$$$g(p,q)=\sum_{i=1}^p {(A_{n+1-i}-A_i)}+\sum_{i=1}^q {(B_{m+1-i}-B_i)}$$$$$$
Here, $$$A$$$ and $$$B$$$ are sorted versions of $$$a$$$ and $$$b$$$. The proof is left as a practice for the reader; if you want a rigorous proof, an approach using the rearrangement inequality might help you.
Then, assuming the value $$$x$$$ is always chosen so that the operations can be performed, the value of $$$f(k)$$$ will be as follows.
$$$$$$f(k)= \max_x{g(x,k-x)}$$$$$$
Now we have two questions to ask ourselves:
• For what values of $$$x$$$ is it impossible to perform the operations?
• How do we maximize this value?
The first is relatively easier. We first return to the definition of $$$g(p,q)$$$, and find specific inequalities from it.
Then, exactly four inequalities can be found as follows:
• $$$2p+q \le n$$$, because otherwise we will use more than $$$n$$$ points on $$$y=0$$$;
• $$$p+2q \le m$$$, because otherwise we will use more than $$$m$$$ points on $$$y=2$$$;
• $$$p \ge 0$$$, trivially;
• $$$q \ge 0$$$, also trivially.
Assigning $$$x$$$ and $$$k-x$$$ to $$$p$$$ and $$$q$$$ for each inequality, we get the following four inequalities:
• $$$2x+k-x = x+k \le n \longleftrightarrow x \le n-k$$$;
• $$$x+2(k-x) = 2k-x \le m \longleftrightarrow x \ge 2k-m$$$;
• $$$x \ge 0$$$;
• $$$k-x \ge 0 \longleftrightarrow x \le k$$$.
Compiling all four inequalities into one inequality, we get the following.
$$$$$$\max(0,2k-m) \le x \le \min(k,n-k)$$$$$$
So now we can easily judge if the operations can be performed for some value $$$x$$$. Also, it is easy to see that when the lefthand bound exceeds the righthand bound, it is impossible to perform $$$k$$$ operations. Thus, here we can derive $$$k_\max$$$. Though it is easy to find a closed form for $$$k_\max$$$, it is not required for this problem.
Now for the next question. Naively computing the values for every $$$x$$$ in the range for all $$$k$$$ takes us $$$\mathcal{O}(nm)$$$ time. How to do it faster?
Again, go back to the definition of $$$g(p,q)$$$. Observe that the value dependent on $$$p$$$ is a prefix sum of a strictly decreasing sequence, and thus is convex. Likewise, the value dependent on $$$q$$$ is also convex. So, given that $$$g(x,k-x)$$$ is a sum of two convex functions of $$$x$$$, $$$g(x,k-x)$$$ is just another convex function of $$$x$$$. Thus, as we already know the range of $$$x$$$, we can perform a ternary search on the range. Note that we are doing ternary search on integers and not on real values, so you might need to take extra care of off-by-one errors.
There are other ways to solve this task (also relying a lot on the convexity), like doing binary search instead of ternary search, or performing two pointers for $$$p$$$ and $$$q$$$. Anyways, the time complexity is $$$\mathcal{O}(n \log n + m \log m)$$$, bounded below by time complexity of sorting.