Subtask 1

Duyệt mọi cách ghép cặp có thể và kiểm tra chênh lệch nhỏ nhất

Subtask 2

• Chia nhị phân chênh lệch nhỏ nhất (gọi là \(X\)).
• Xây dựng đồ thị \(2\) phía với \(C[i, j] = 1\) nếu chênh lệch giữa \(B_{i}\) và \(G_{j}\) không quá \(X\).
• Kiểm tra bộ ghép cực đại có đạt độ lớn là \(K\) không, nếu không đạt thì tăng \(X\), nếu đạt thì giảm \(X\)

Độ phức tạp \(\log(10^{9}) \times\) độ phức tạp tìm cặp ghép

Subtask 3

Tương tự như subtask \(2\), nhưng cần tối ưu đoạn tìm cặp ghép. Một cách làm khác là:

• Sắp xếp mảng \(B\) và \(G\).
• Chia nhị phân chênh lệch nhỏ nhất
• Quy hoạch động \(F[i, j]\) là số cặp nhiều nhất khi xét \(i\) bạn nam đầu tiên, và \(j\) bạn nữ đầu tiên:
  • \(F[i, j] = F[i - 1, j - 1] + 1\) nếu \(|B_{i} - G_{j}| \leq X\).
  • \(F[i, j] = \max(F[i - 1, j], F[i, j - 1])\) trong trường hợp ngược lại.

Độ phức tạp \(O(\log(10^{9}) \times B \times G)\).

Subtask 4

Trường hợp \(k = 1\), ta cần tìm \(2\) phần tử \(i\) và \(j\) sao cho \(|B_{i} - G_{j}|\) nhỏ nhất. Có nhiều cách làm, một trong số đó là:

• Sắp xếp mảng \(B\) và mảng \(G\).
• Xét từng giá trị \(B_{i}\), khi đó, chênh lệch \(|B_{i} - G_{j}|\) tạo thành hàm lồi.

Cách làm này độ phức tạp \(O(B \log B + G \log G + B \log G)\).

Một cách cải tiến bước \(2\) là rút ra nhận xét: Giả sử, với \(i\), ta tìm được vị trí \(j\) tốt nhất (gọi là $j * $). Bước tiếp theo với \(i + 1\), vị trí tốt nhất tìm được chắc chắn phải \(\geq j* \Rightarrow\) ta có thể tìm \(j\) tuyến tính.

Subtask 6

• Sắp xếp mảng \(B\) và mảng \(G\).
• Chia nhị phân giá trị \(X\) là chênh lệch lớn nhất
  • Khi đó \(B_{i}\) có thể ghép với bất kì \(G_{j}\) nào trong đoạn \([B_{i} - X, B_{i} + X]\).
  • Nhận thấy ta có \(B\) đoạn bằng nhau để ghép \(G\) giá trị vào và các đoạn này đã được sắp xếp tăng dần.
  • Tham lam, đi từ đoạn nhỏ đến đoạn lớn, nếu gặp giá trị \(j\) nào phù hợp thì ghép luôn.

Độ phức tạp: \(O(B \log B + G \log G + \log(10^{9}) \times (B + G)\).