An Animal Contest 2 P4 - Koala Gambling - DMOJ: Modern Online Judge

An Animal Contest 2 P4 - Koala Gambling

Points: 12

Time limit: 1.2s

Java 2.4s

Python 2.4s

Memory limit: 256M

Author:

WilliamWu277

Problem types

The koalas enjoy playing all kinds of games with each other. One such game is played in the shifty koala underground, where fortunes can be lost or won in a single moment.

The game begins with a list of $N$ ~N~ numbers $a$ ~a~, arranged into a row. Two players take turns picking either the number at the beginning or end of the row. In this variation of the game, each koala tries to maximize the sum of all the values that they pick. As the koalas have been playing this game since the beginning of time, they are masters and will always play optimally. Keen Ken Googler the Keen koala is keen to kollect as much kash as possible. Given his friendliness with the card dealer, he can arrange the $N$ ~N~ numbers in any way that he wants before playing against his unfortunate victim. As a holder of the premium gamer club member card, he also always goes first.

However, Keen Ken is not very good at games, so he asks you to help him rearrange the $N$ ~N~ numbers in $a$ ~a~ into an arrangement $b$ ~b~ such that he will always win if he plays optimally. Since Keen Ken has a lot of players to scam, help him do this $T$ ~T~ times!

Keen Ken wins the game if the sum of all his chosen numbers is strictly greater than the sum of his opponent's numbers.

For this problem, Python users are recommended to use PyPy over CPython.

Constraints

$1 \le T \le 5 \cdot 10^3$ ~1 \le T \le 5 \cdot 10^3~

$1 \le N \le 600$ ~1 \le N \le 600~

$1 \le a_i \le 10^9$ ~1 \le a_i \le 10^9~

Input Specification

The first line contains the integer $T$ ~T~, the number of cases you are to solve.

Each test case consists of two lines. The first contains $N$ ~N~ for that specific test case, followed by $N$ ~N~ space-separated integers $a_i$ ~a_i~ on the next line.

Output Specification

Output $T$ ~T~ lines, each containing $N$ ~N~ space-separated integers $b_i$ ~b_i~. Note that any arrangement suffices as long as Ken wins if he plays optimally. If Keen Ken cannot win, output $-1$ ~-1~.

Note: There should be no trailing whitespaces after each line and the output should end with a newline.

Sample Input 1

1
5
8 6 2 8 1

Sample Output 1

8 2 6 8 1

Explanation for Sample 1

At the end of the game, Ken receives a score of $15$ ~15~ from the numbers $8$ ~8~, $6$ ~6~, and $1$ ~1~. The other player ends with a score of $10$ ~10~, using $2$ ~2~ and $8$ ~8~. We see that $15$ ~15~ is greater than $10$ ~10~ so Ken wins.

Sample Input 2

1
6
4 7 4 6 8 3

Sample Output 2

6 7 4 4 8 3

Comments

1

zenomyth commented on Oct. 14, 2023, 11:52 p.m.

For the same logic I got TLE with C++ but AC with Pypy3. And this is not due to the looser limit for python because run time for Pypy3 is even less than C++. This is weird.

0

SimonV commented on Jan. 2, 2024, 7:53 p.m.

I had the same issue, TLE with C++ but AC with Pypy3

2

Kirito commented on Jan. 3, 2024, 2:31 a.m.

std::cin is quite slow; either use C's scanf or add std::cin.tie(0)->sync_with_stdio(0) to avoid avoid getting TLE.