Maximum number of crossed matchings between two sequences

Back to OJ problems …

Problem

Given two sequences of integers, $A=a_1,a_2,a_3...$ and $B=b_1,b_2,b_3...$ , we are allowed to match an integer $a_i$ from the first sequence with an integer $b_j$ from the second sequence only if $a_i=b_j$ . No integer in either sequence can be matched with more than one integer in the other sequence.

Each matching must cross with another one and only one different matching. Two matchings $(a_i,b_j)$ and $(a_k,b_l)$ are considered crossed iff $i<k$ and $l<j$ , or if $k<i$ and $j<l$ . The two matchings are considered different iff $a_i\neq a_k$ .

We are required to know the maximum number of crossed matchings that can be done. For example, in the following figure, the maximum is 4.

Solution

The key to solve this problem is to notice its similarity to the well-known longest common subsequence (LCS) problem. However, while the LCS problem asks for the maximum number of uncrossed matchings, this problem asks for the maximum number of crossed matchings.

Let $A_m$ be a sequence that contains the first $m$ elements of $A$ in order. Similarly, $B_n$ is a sequence that contains the first $n$ elements of $B$ in order. Let $MCM(A_m,B_n)$ be the maximum number of crossed matchings between the two sequences $A_m$ and $B_n$ . We define the the predicate $boundary(A_m,B_n)$ to be true if and only if there is a crossed matching between $A_m$ and $B_n$ that involves the last element of $A_m$ and the last element of $B_n$ ; that is,

$boundary(A_m,B_n) \Leftrightarrow\ a_m\neq b_n\wedge (\exists\ i<m\ \exists\ j<n\ (a_m=b_j\wedge b_n=a_i))$

The importance of this predicate is that it determines whether adding/dropping the last element in $A_m$ or $B_n$ will add/drop a crossed matching. If the predicate $boundary(A_m,B_n)$ is satisfied, then we are interested to know what elements are involved in this boundary crossed matching. Let $l\_idx(A_m, b_n)$ denote the index of the last occurrence of $b_n$ in $A_m$ ; that is, $l\_idx(A_m,b_n)=\displaystyle\max\{i:i<m\ and\ a_i=b_n\}$ . Similarly, $l\_idx(B_n,a_m)=\displaystyle\max\{j:j<n\ and\ b_j=a_m\}$ is the index of the last occurrence of $a_m$ in $B_n$ . If we are going to count this boundary crossed matching in our maximal set of crossed matchings, then we will have to uncount any other crossed matchings that involve elements between $l\_idx(A_m,b_n)$ and $a_m$ inclusive, or elements between $l\_idx(B_n,a_m)$ and $b_n$ inclusive. This effectively means going back to $MCM(A_{l\_idx(A_m,b_n)-1},B_{l\_idx(B_n,a_m)-1})$ . Therefore we shouldn’t count a boundary crossed matching unless there are no other crossed matchings that will be uncoutned for this purpose. We define $MCM$ recursively as follow:

Function $MCM(A_m,B_n)$
$\$ If $m=0$ or $n=0$ Then Return $0$
$\$ $res\leftarrow max(MCM(A_m,B_{n-1}),MCM(A_{m-1},B_n))$
$\$ If $boundary(A_m,B_n)$ Then
$\$ $\$ $res\leftarrow\max(res, MCM(A_{l\_idx(A_m,b_n)-1},B_{l\_idx(B_n,a_m)-1})+1)$
$\$ Return $res$