Problem author: Nils Gustafsson.

Subtasks may not be ordered for ease of discussion.

The Problem

There are ~N~ generals numbered ~0, 1, \dots, N-1~ which you want to arrange in a row. The ~j~-th general ranks all generals ~i~ such that ~i < j~, and it is forbidden for two generals ~i~ and ~j~ (~i < j~) to stand next to each other in the row if general ~i~ is strictly in the second half of general ~j~'s ranking.

Construct a way to arrange the ~N~ generals in a row such that the restrictions are satisfied. It is guaranteed that there is a solution.

Subtask 3

In general, if one doesn't have the idea for the full solution, it is always nice to start with brute force.

It is easy to see that there are ~N! = 1 \times 2 \times \dots \times N~ ways to order the generals. When ~N \le 8~, ~N! \le 40\,320~. Therefore one can simply brute force all the possible orders and do checking. This brute force can be implemented recursively, or by iterating through all permutations (for example by using next_permutation in C++).

Note that when we say general ~i~ and general ~j~ cannot stand next to each other, that means general ~i~ cannot be directly to the left of general ~j~, and vice versa.

Subtask 1

Maybe we can start with some smaller ~N~ and work our way to larger ~N~. Let's just run the brute force written in subtask 3.

Let's say the brute force returns the lexicographically smallest solution. Then, for different ~N~ you should get the following constructions:

• ~N = 2~: 0 1
• ~N = 3~: 0 1 2
• ~N = 4~: 0 1 2 3
• ~N = 5~: 0 1 2 3 4

It seems that the solution to a certain ~N~ is ~0, 1, \dots, N-1~. It is easy to see why it works, as ~p_{i,0} = i-1~ and hence generals ~i-1~ and ~i~ can always stand next to each other.

Subtask 2

Let's use the brute force again.

• ~N = 2~: 0 1
• ~N = 3~: 1 0 2
• ~N = 4~: 1 3 0 2
• ~N = 5~: 2 0 3 1 4
• ~N = 6~: 2 5 0 3 1 4
• ~N = 7~: 3 0 4 1 5 2 6
• ~N = 8~: 3 7 0 4 1 5 2 6

It seems that the solution to odd ~N~ is:

• Arrange generals ~\frac{N-1}{2}, \frac{N-1}{2}+1, \dots, N-1~ in that order
• Put general ~0, 1, \dots, \frac{N-3}{2}~ in between each pair of adjacent generals

The difference of the numbers of adjacent generals are either ~\frac{N-1}{2}~ or ~\frac{N-1}{2}+1~. Since ~p_{i,j} = j~, each general favors generals with smaller numbers. Hence it is easy to see that a difference of ~\frac{N-1}{2}~ or ~\frac{N-1}{2}+1~ does not violate the constraints.

For even ~N~, simply add general ~N-1~ in between the first two generals, which are general ~\frac{N}{2}-1~ and general ~0~ respectively. It is also easy to see that adding general ~N-1~ this way does not violate the constraints.

Full Task

Induction

We can think of the construction in Subtask 1 in another way: start with the construction for ~N = K~ and add general ~K~ somewhere in the row to find the correct construction for ~N = K+1~. This induction-like technique turns out to be useful in solving the full task.

Proving the Existence of a Solution

Note that if there is a way to insert general ~K~ in a row containing generals ~0, 1, \dots, K-1~ currently (regardless of how they are arranged), and there is a construction for ~N = 2~, then there is a construction for all valid inputs. This is because one can get the construction for ~N = K+1~ easily from ~N = K~, by adding general ~K~ into the current row.

Now, how many ways are there to insert general ~K~? Since there are ~K~ generals in the row currently, there must be ~K+1~ ways that general ~K~ can be inserted. Additionally, ~\lceil \frac{K}{2} \rceil~ of the existing generals can be placed next to general ~K~, while the rest cannot. Let's call the generals that can be placed next to general ~K~ "good" generals, and the rest "bad" generals.

We want to find one of the following:

• A pair of adjacent generals such that both of them are good (condition 1)
• Either the first or the last general that is good (condition 2)

Now, assume the contrary that neither of these two conditions are true. Then, the first and last generals are bad, and between every pair of good generals there is at least one bad general. There are ~\lceil \frac{K}{2} \rceil~ good generals, so we need at least ~\lceil \frac{K}{2} \rceil+1~ bad generals for this to occur. But we also know that the number of bad generals equals ~\lfloor \frac{K}{2} \rfloor~, and ~\lceil \frac{K}{2} \rceil+1 \ne \lfloor \frac{K}{2} \rfloor~.

We found a contradiction, hence the assumption that "neither of the two conditions are true" is false. Therefore, at least one of the conditions is true, and that means we can always find a way to insert general ~K~.

Constructing the Solution

Start with ~2~ generals, then add each new general by exhausting each possible position the new general can be in.

The time complexity is ~\mathcal O(N^2)~.

Aftermath

Here are some questions you may think about after attempting this task, if you are interested:

• If we instead give ~K~ constraints in the form ~(a, b)~, such that ~a~ and ~b~ cannot stand next to each other, where ~0 \le K \le \frac{N(N-1)}{2}~, is the general problem solvable in polynomial time? Alternatively, can you reduce it to a standard NP-complete problem?
• What if we impose additional constraints on the arrangement of the generals, such as requiring that certain pairs of generals must stand next to each other or that certain generals must be placed in specific positions?