Maximum Winning Arrangement

Difficulty: Hard

You are given an array nums of n distinct integers.

Choose a permutation A of nums.
It will be tested against every possible permutation B of nums.

Both A and B are queues. Initially, A has priority.

Repeat the following process until one queue becomes empty:

1. Pop the front numbers a and b from both queues.
2. The larger number survives.
3. If a == b, the number from the priority queue survives.
4. The other number is removed.
5. If the survivor came from the priority queue, update it as:

survivor = max(1, survivor - ceil(survivor * 10 / 100))

6. If the survivor came from the non-priority queue, update it as:

survivor = max(1, survivor - ceil(survivor * 50 / 100))

Then that queue becomes the new priority queue.

7. Push the survivor to the back of its queue.

If B becomes empty, A wins.
If A becomes empty, A does not win.

For a permutation A, define:

winCount(A) = number of B permutations that A wins against

Return the lexicographically smallest permutation A with the maximum winCount.

Example

Input:

nums = [50, 64, 79, 109, 135, 181]

Output:

[135, 181, 79, 109, 50, 64]

Explanation:

Among all permutations of A, this arrangement wins against the largest number of possible B permutations.

Constraints

3 <= nums.length <= 16
50 <= nums[i] <= 330
All nums[i] are distinct.

Follow-up

Let n = nums.length.

The brute force approach compares every permutation of A with every permutation of B, which takes:

O((n!)^2)

Can you find the best arrangement without comparing every pair of permutations?