Turtle
Contest: Codeforces Round 594 (Div. 1)
Difficulty rating: 3100
Tags: dp, implementation

Kolya has a turtle and a field of size $$$2 \times n$$$. The field rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom, while the columns are numbered from $$$1$$$ to $$$n$$$ from left to right.

Suppose in each cell of the field there is a lettuce leaf. The energy value of lettuce leaf in row $$$i$$$ and column $$$j$$$ is equal to $$$a_{i,j}$$$. The turtle is initially in the top left cell and wants to reach the bottom right cell. The turtle can only move right and down and among all possible ways it will choose a way, maximizing the total energy value of lettuce leaves (in case there are several such paths, it will choose any of them).

Kolya is afraid, that if turtle will eat too much lettuce, it can be bad for its health. So he wants to reorder lettuce leaves in the field, so that the energetic cost of leaves eaten by turtle will be minimized.

Input format:
The first line contains an integer $$$n$$$ ($$$2 \le n \le 25$$$) — the length of the field.

The second line contains $$$n$$$ integers $$$a_{1, i}$$$ ($$$0 \le a_{1, i} \le 50\,000$$$), the energetic cost of lettuce leaves in the first row of the field.

The third line contains $$$n$$$ integers $$$a_{2, i}$$$ ($$$0 \le a_{2, i} \le 50\,000$$$), the energetic cost of lettuce leaves in the second row of the field.

Output format:
Print two lines with $$$n$$$ integers in each — the optimal reordering of lettuce from the input data.

In case there are several optimal ways to reorder lettuce, print any of them.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
In the first example, after reordering, the turtle will eat lettuce with total energetic cost $$$1+4+2 = 7$$$.

In the second example, the turtle will eat lettuce with energetic cost equal $$$0$$$.

In the third example, after reordering, the turtle will eat lettuce with total energetic cost equal $$$1$$$.

Example input:
2
1 4
2 3

Example output:
1 3 
4 2

Example input:
3
0 0 0
0 0 0

Example output:
0 0 0 
0 0 0

Editorial:
Consider that we already fixed the set in the top line and fixed.
If we perform a swap in this situation, the answer will clearly won't become worse (some paths are not changing, and some are decreasing).
So we can assume that the first line is sorted, and similarly the second line is sorted too (but descending).
Now let's think which path the turtle will choose. Observe the difference between to paths:
Then cost of path $$$i+1$$$ minus cost of path $$$i$$$ is equal to $$$x_{i+1} - y_{i}$$$.
$$$x_i$$$ increases when $$$i$$$ increases, $$$y_i$$$ decreases, $$$x_{i+1} - y_{i}$$$ decreases, so the discrete derivative increases.
Such function looks like:
So clearly the turtle will choose either the first or the last path.
So now we need to split our set into two of equal size, so that the maximum sum is smallest possible.
This is a knapsack problem. The states are the prefix of elements considered, the number of elements taken, the weight. It works in $$$\mathcal{O}(n^3 maxa)$$$
EDIT: it turned out it was inobvious... The corner cells take two minimal elements and are not considered in knapsack since they are contained in all paths. It's easy to prove that it's optimal to put minimal elements in corners.