# Hamiltonian Path in Tournament

This is a classical problem in math circles. What surprised me is how difficult it was to find an online judge to submit it.

In this editorial, I will present various solutions. You will quickly come to see that almost comparison-based algorithm you can think of can be generalized to tournaments. The most educational one is the binary insertion sort one; I would strongly recommend you understand it.

First, a generally nice insight that is given in the problem statement: every tournament has a hamiltonian path. Some of these algorithms work as constructive proofs of this fact.

# ~${N \choose 2}=124750$ queries
In this subtask, we can afford to read the entire graph explicitly. If you're aiming for this subtask, you might as well; otherwise, you risk using too many queries if you aren't careful.

First, we must realize that this problem is intimately tied to sorting. In a way, it might be viewed as a generalization of it: if there is a total order (we can orient all vertices on a line such that all outgoing edges point right), then this is just comparison-based sorting.

## Insertion Sort
Let's build our path one node at a time. It turns out that if we have a path, it is always possible to extend. Let's see how to extend it with a new node.

Suppose we have the following partial path

and we now wish to insert a vertex $u$. Some obvious edges to try are $t \rightarrow u$ and $u \rightarrow s$: if any of these edges are directed these ways, we can easily insert $u$ into the path.



Thus, the case we haven't handled is the following one:


Let's try to insert it into the middle somewhere like this:


Will this always work? Yes! We are looking for any adjacent pair of nodes in the path, where the first one points into $u$, and $u$ then points into the other one. Let's say that a node in the path is $1$-node if it points into $u$, and $0$ otherwise. We thus get a binary string from the path:


So, we are looking for the substring $10$. Note that this must always exist in the "hard" case: in this case, the start of the string is $1$, and the end $0$. Thus, there must be some point where we switch from $1$ to $0$, which is where we can insert $u$.

## Bubble Sort
Bubble sort also works: start with a permutation, and then make adjacent swaps if edges point "left". Proving that this works is a nice exercise.

# Quicksort: $~5400-6000$ queries
Quicksort is widely-recognized as one of the fastest sorting algorithms. Let's try it. Let's select an arbitrary vertex $p$, and ask every other vertex for the direction of the edge between them.


This splits the graph into two sets: those pointing into $p$, and those that $p$ point to. We can then find a hamiltonian path in each part independently (recall that every tournament has a hamiltonian path), and then connect them with $p$:


Because every vertex has an edge into $p$ in the left part, we can definitely connect it with $p$. A similar argument holds for the right part.

Analyzing this is quite tricky. In general, you should avoid using quicksort for interactive problems when possible, as it carries a worse constant factor than most other sorting algorithms.

# Segment tree-optimized selection sort

I have not implemented these, but I am quite certain that both this and heapsort can be generalized to sort tournaments.

# Binary insertion sort: ~$4800$ queries
In the insertion sort algorithm, the subproblem using a lot of queries was finding the substring $10$ in a string starting with $1$ and ending with $0$. This subproblem can be solved using binary search!

Suppose our string is $S$ and we query $S[i]$. If $S[i]=1$, then we know that there will be an index to the right of $i$ where a switch from $1$ to $0$ occurs. Similarly, if $S[i]=0$, then there will be a point to the left where the switch occurs.

n=int(input())

def ask(a,b):
    print(f"? {a+1} {b+1}", flush=True)
    return int(input())

p = [0]
for i in range(1, n):
    if ask(p[-1], i) == 1:
        p.append(i)
        continue
    if ask(i, p[0]) == 1:
        p.insert(0, i)
        continue
    l, r = 0, len(p) - 1
    while l < r:
        m = (l + r) // 2
        if ask(p[m], i) == 1:
            l = m + 1
        else:
            r = m
    p.insert(l, i)

print("!", *(x + 1 for x in p))

# Optimized binary insertion sort: ~$3990-3810$ queries
It turns out that we don't *really* need to ask the front and end of our path: if any of the "easy" cases occurs, then the binary search will either get "lucky" and find a solution in the middle, or drift towards one of the edges, which is then a valid insertion point.

To further improve the solution, note that the judge is not adaptive. Thus, shuffling the order of nodes to insert into our permutation helps us get away from the worst-case (yes, there is data tailored to a couple of fixed orders).

# Merge sort: ~$3950-3880$ queries
Merge sort can be generalized to work for tournaments: we can take two paths and merge them in a linear number of comparisons.

By shuffling the node labels, we decrease query count to ~$3880$.

# Honorable mention: standard library sorts

## Timsort: ~$3835$ queries

Amazingly enough, Python's builtin sort correctly manages to sort in tournaments:

from functools import cmp_to_key

n = int(input())

def compare(a, b):
    print(f"? {a+1} {b+1}", flush=True)
    res = int(input())
    
    ans = -1 if res == 1 else 1
    return ans

perm = list(range(n))
perm.sort(key=cmp_to_key(compare))
print("!", *(x + 1 for x in perm))

## `std::stable_sort`: $4450$ queries
C++'s `stable_sort` also works decently well.
## `std::stable_sort`+cache: $4319$ queries
## `std::stable_sort`+cache+shuffling before sort: $4319$ queries

# Ford-Johnson+random (merge insertion sort): ~$3795$ queries

One way to get full points is using the Ford-Johnson algorithm. I will provide a standalone description of it.

First, shuffle the order of all elements to avoid adversarial worst cases. We will then solve the problem using divide and conquer: the function `solve(nodes)` takes a set of nodes and returns a permutation of them that forms a hamiltonian path. Let's describe `solve`.

Start by asking $(1,2)$, $(3,4)$, $...$. (In reality, we of course ask `(nodes[0], nodes[1])`, ..., but let's relabel them for convenience)


We now get lots of paths of length 2. If $|nodes|$ is odd, there will be one node that is not grouped, called the straggler. We will explain how to handle it later. Now, call solve to create a hamiltonian path of all the nodes that "win" each pair (a node $u$ beats $v$ if the edge is directed $u \rightarrow v$).


Note that we can insert the bottom-right node (highlighted in red) into the path for free (this saves about 30 questions!). Now, the final step is to insert the nodes not in the path into the path one by one.

A naive way to do this is to shuffle their order and insert them one by one using binary search across the entire path. We also insert the straggler using binary search. This gets us about $4240$ questions, which is not great. However, this is inefficient: if we go backwards, then we can safely only binary search over the suffix including the node.


For example, suppose we want to insert the red node (this is the first one, the green ones we get for free). Then, we only need to binary search to the right of the red line.

This gets ~$3820$ questions, about the same as randomized binary insertion sort. The way to optimize this is to realize that this insertion order is not optimal. Whenever we insert an item, the binary search bound for all elements to the left of it increases by 1. Thus, a better order might be something like this


Let's see how to optimally partition the array into intervals where we go left to right.
The binary search i use

to_insert = ...
l, r = L, R
while l < r:
    m = (l + r) // 2
    if ask(path[m], to_insert) == 1:
        l = m + 1
    else:
        r = m

takes exactly $\lceil \log_2(R-L) \rceil$ iterations. This is enough to write a DP for the optimal group sizes. We can afford to be lazy and let it run in $O(N^2)$.

$$DP[i]=\text{min cost to insert i elements}=\min_{2 \leq j \leq i} \left( DP[j] + (i-j) \cdot \lceil \log_2(i+j) \rceil \right)$$

where $DP[0]=DP[1]=DP[2]=0$ because of the two free elements.

With this, get somewhere around $3795$ queries on average, which will definitely get full points if you submit twice (I've never seen it exceed $3800$ in testing). Unless you have a bug and your true average is higher, of course.

Note that it's possible to compute the optimal block sizes that this DP gives us in linear time: see the [wikipedia page](https://en.wikipedia.org/wiki/Merge-insertion_sort#Algorithm). Whether the DP or analytic solution is easier to get right is probably up to personal preference. Also note that we can't really do anything fancy with the straggler element (the one left over if the number of nodes is odd), so we can just insert it using binary search over the entire path at the end.

# Beyond
There are better approaches that can push the query amount down to ~$3790$. https://arxiv.org/pdf/1705.00849. The theoretical limit is $\log_2(500!) \approx 3767$.