Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of M players, numbered $1, 2, \dots , M$. You have $N$ players, numbered $1, 2, \dots , N$ from which to choose your team, where $N \geq M$. Each of the $M$ players from the visiting team must be paired up with one of your $N$ players. The tournament rules insist that the pairings must respect the order that has been fixed for both teams. That is, when you pick players $i_1, i_2, \dots i_M$, to play against opponents numbered $1, 2, \dots , M$, it must be the case that $i_1 < i_2 < \dots < i_M$, in terms of the order $1, 2, \dots , N$ in which your players are listed.
You want to ensure a good fight, so you plan to pick your team so that the teams are as
evenly balanced as possible. Each player $j$ on your team has a numerical score $Y S(j)$ that represents his or her playing ability. Likewise, each player $i$ in the opponent team has a playing ability indicated by a numerical score $OS(i)$. The difference in strength between a player $i_j$ from your team and his or her opponent $j$ on the visiting team is the absolute value $\mid Y S(i_j ) − OS(j) \mid$. The imbalance of a pairing is the sum of these differences across all M match-ups in the pairing. Your aim is to minimize this imbalance.
For instance suppose you have six players, whose strengths are as follows.
$\begin{array}{|c|c|c|c|c|c|c|} \hline i & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline YS(i) & 2 & 3 & 4 & 1 & 5 & 7 \\ \hline \end{array}$
Also, suppose that the visiting team has three players, whose strengths are as follows.
$\begin{array}{|c|c|c|c|} \hline i & 1 & 2 & 3 \\ \hline OS(i) & 2 & 9 & 2 \\ \hline \end{array}$
In this situation, the most balanced pairing is $(1,1)$, $(3,2)$ and $(4,3)$, which yields an imbalance of
$\mid Y S(1) − OS(1)\mid+\mid Y S(3) − OS(2) \mid+\mid Y S(4) − OS(3) \mid = \mid 2 − 2 \mid + \mid 4 − 9 \mid + \mid 1 − 2 \mid = 6$
Propose an efficient algorithm to solve this problem and analyse its complexity.
