If we represent the tournament as a binary tree, the leaves correspond to the players, and the internal nodes correspond to matches, forming a complete binary tree.

Let’s consider how to solve the problem when arbitrarily assuming the outcomes of the matches. Assign each player’s original \(l_i\) to the leaves, and for the internal nodes, write the \(r_i\) of the player who loses in that match (the root has the \(r_i\) of both players). Let the modified \(l_i\) and \(r_i\) be \(l_i'\) and \(r_i'\). The condition to complete the tournament is that for all pairs \(u, v\) where nodes labeled with \(r_u\) and \(l_v\) have an ancestor-descendant relationship, it holds that \(l'_v \leq r'_u\). Also, we find that it’s optimal to make the player with the larger \(r_i\) win the match.

We decide to adjust \(l_i' = l_i - x_i\) and \(r_i' = r_i + y_i\).

• \(\mathrm{minimize} \sum x_i + \sum y_i\)
• \(\mathrm{s.t.}\ x_v + y_u \geq l_v-r_u, x_i\geq 0, y_i\geq 0\)

This linear programming problem has an integer solution because the coefficient matrix is totally unimodular, and it matches the original problem. The dual problem is:

• \(\mathrm{maximize} \sum (l_v-r_u)z_{u,v}\)
• \(\mathrm{s.t.}\ \sum z_{i,*} \leq 1, \sum z_{*,i} \leq 1, z_{i,j}\geq 0\)

This is a maximum-weight bipartite matching problem where the weight between \(u\) and \(v\) is \((l_v - r_u)\).

We can solve this problem on the binary tree by defining \(\mathrm{dp}_{i,j}\) as “the maximum total weight when the current node is \(i\), and there are \(j\) unmatched nodes on the \(l_v\) side,” and adding \(l_v\) and \(-r_u\) to the total weight when we decide to use \(l_v\) and \(r_u\) for matching. Here, unmatched nodes can only be matched with their ancestor’s \(r_u\), and the number of such nodes is at most \(N + 1\), so we can limit the range of \(j\) to at most \(N + 1\). At this point, the problem can be solved in \(\mathrm{O}(N^2 2^N)\) time, but by further limiting the range of \(j\) to the smaller of the number of leaves in the subtree rooted at that node and \(N + 1\), we can reduce it to \(\mathrm{O}(N 2^N)\) (commonly known as tree DP in \(\mathrm{O}(NK)\)).