Official

B - Increasing Triples Editorial by evima

Let us call a tuple \((A_i, B_j, C_k)\) such that \(A_i < B_j < C_k\) simply a triple. The problem can be rephrased into choosing as many triples as possible under the restriction that each element can be used at most once.

Below, we assume that \(A_1\leqq \cdots\leqq A_N\), \(B_1\leqq \cdots\leqq B_N\), and \(C_1\leqq \cdots\leqq C_N\), by sorting the input.

Let us call a situation an optimal solution where the maximum possible number of triples are chosen.

◆ The structure of optimal solutions (1)

We can show that one of the following holds.

  • The optimal solution chooses no triple.
  • There exists an optimal solution that chooses \(A_i\).

Let us prove this.

Assume that there is an optimal solution choosing one or more triples without using \(A_1\). We can replace one of the chosen triples in such an optimal solution, \((A_i, B_j, C_k)\), with \((A_1, B_j, C_k)\). This does not change the number of chosen triples, so an optimal solution remains an optimal solution. Thus, we can see that there exists an optimal solution choosing \(A_1\).

From this, we can see that we only need to consider the case \(A_1\) is chosen.

◆ The structure of optimal solutions (2)

Next, let us think about the choice of \(B_j\).

We cannot use \(B_j\) such that \(B_j\leq A_1\) in our triples. Thus, we can delete these \(B_j\) in the first place and move on.

The case \(B\) is empty is trivial, so let us assume otherwise. That is, we assume \(A_1 < B_1\).

We can show that one of the following holds.

  • The optimal solution chooses no triple.
  • There exists an optimal solution that uses \(A_1\) and \(B_1\) in the same triple.

Let us prove this.

Assume that there is an optimal solution choosing one or more triples without using \(A_1\) and \(B_1\) in the same triple. From this, if we can show that there exists an optimal solution that uses \(A_1\) and \(B_1\) in the same triple, we are done. First, similarly to the proof in (1), we can show that there exists an optimal solution that uses both \(A_1\) and \(B_1\) in some triples. Now, assume that \(A_1\) and \(B_1\) are not in the same triple, and they belong to triples \((A_1, B_j, C_k)\) and \((A_i, B_1, C_{k'})\), respectively. Because of the minimumness of \(B_1\), we can rearrange these triples into \((A_1, B_1, C_{k'})\) and \((A_i, B_j, C_k)\), yielding an optimal solution that uses \(A_1\) and \(B_1\) in the same triple.

◆ The structure of optimal solutions (3)

We cannot use \(C_k\) such that \(C_k\leqq B_1\) in our triples. Thus, we can delete these \(B_j\) in the first place and move on assuming that \(A_1 < B_1 < C_1\).

Similarly to (1) and (2), we can prove the following:

  • There exists an optimal solution that uses \(A_1\), \(B_1\), and \(C_1\) in the same triple.

◆ Solution

Summing up the above, we obtain the following greedy algorithm.

  • If \(A\) is empty, terminate. Otherwise, let \(A_1\) be the minimum value among \(A\), and delete all \(B_j\) that are not greater than \(A_1\).
  • If \(B\) is empty, terminate. Otherwise, let \(B_1\) be the minimum value among \(B\), and delete all \(C_k\) that are not greater than \(B_1\).
  • If \(C\) is empty, terminate. Otherwise, let \(C_1\) be the minimum value among \(C\).
  • Choose the triple \((A_1, B_1, C_1)\). Delete \(A_1, B_1, C_1\) and go back to the beginning.

By efficiently retrieving and deleting the minimum values, we can solve the problem in \(\Theta(N\log N)\) time.

There are several ways to implement the algorithm, such as the following.

posted:
last update: