Tóm tắt đề bài

Cho một dãy số ~a~ biểu đạt giá trị của các đồ chơi, là hoán vị từ 1 đến ~2 \times N~. Đồ chơi của Bờm có giá trị từ ~a_1~ đến ~a_N~, đồ chơi của cuội có các giá trị còn lại.

Luật chơi như sau:

• Hai người lần lượt chọn món đồ từng ván, mỗi người chỉ dùng món đồ chơi đúng 1 lần.
• Người có đồ chơi có giá trị lớn hơn thì thắng.

Hỏi trong trường hợp may mắn nhất, hay trường hợp Cuội không biết chơi và Bờm có thể can thiệp toàn bộ, Bờm có thể thắng được bao nhiêu ván?

Subtask 1. ~n \le 100~

Subtask này chỉ với mục đích chứng minh tính đúng đắn của thuật tham lam trong subtask 2, và có thể sử dụng nhiều kiến thức ngoài phạm vi của kỳ thi Tuyển sinh 10.

Gọi ~B = {b_1, b_2, ..., b_N}~ là danh sách đồ chơi của Bờm.

Gọi ~C = {c_1, c_2, ..., c_N}~ là danh sách đồ chơi của Cuội.

Ta dựng đồ thị hai phía, với đỉnh thứ ~i~ của Bờm nối với đỉnh thứ ~j~ của Cuội khi ~b_i > c_j~. Điều này có nghĩa, đỉnh ~i~ của Bờm nối với đỉnh ~j~ của Cuội nếu đồ chơi thứ ~i~ của Bờm có thể thắng đồ chơi thứ ~j~ của Cuội.

Có thể thấy, ta cần tìm cặp ghép cực đại trên đồ thị hai phía này, và đó cũng là kết quả.

Độ phức tạp: ~O~ (~n^3~).

Subtask 2. ~n \le 50000~

Gọi ~B = {b_1, b_2, ..., b_N}~ là danh sách đồ chơi của Bờm đã được sắp xếp tăng dần.

Gọi ~C = {c_1, c_2, ..., c_N}~ là danh sách đồ chơi của Cuội đã được sắp xếp tăng dần.

Ta lưu ~i~ là chỉ số hiện tại của Bờm, và ~j~ là chỉ số hiện tại của Cuội. Với mỗi ~j~, ta tìm ~i~ nhỏ nhất sao cho ~a_i > b_j~, sau đó ghép cặp. Với các phần tử ~j~ mà ta không tìm ra ~i~ thỏa mãn nữa, ta sẽ chấp nhận Bờm thua.

Có thể chứng minh đây luôn là cách làm tối ưu.

Độ phức tạp: ~O~ (~n~).

Chứng minh:

Gọi ~M~ là cặp ghép cực đại như trong thuật toán ở subtask 1. Gọi ~K = |M|~. Giả sử trong cặp ghép cực đại này ta có các bộ ta chọn là (~b_{i_1}, c_{j_1}~), (~b_{i_2}, c_{j_2}~), ..., (~b_{i_k}, c_{j_k}~). và ~b_{i_x} > c_{i_x}~.

Xét ~b_1~ và ~c_1~.

Trường hợp 1. ~b_1 > c_1~.

• Nếu ~b_1 > c_1~, thì thuật toán tham lam sẽ ghép (~b_1, c_1~).
• Trong cặp ghép cực đại ~M~ nói trên, có ba khả năng:
  • Trường hợp 1. Cặp ghép đó đã ghép ~c_1~ với ~b_x~ nào đó nhưng ~x > 1~. Vì ~b_1 < b_x~, nên ta có thể đổi cặp (~b_x, c_1~) thành ~(b_1, c_1)~ mà không làm mất tính hợp lệ hay giảm tính tối ưu của kết quả.
  • Trường hợp 2. Cặp ghép đó không ghép ~c_1~ với bất kỳ ~b_x~ nào. Với trường hợp này, ta có thể sửa ~M~: thay đổi một cặp ~c_{j_t}~ nào đó với ~t > 1~ để đưa ~c_1~ ghép với ~b_1~. Như vậy, kể cả ~M~ không dùng ~b_1~ thì ta vẫn tạo ra một cặp ghép cực đại mới với cùng kích thước, mà lại có cặp (~b_1, c_1~).
  • Trường hợp 3. Cặp ghép đó đã ghép ~b_1~ với ~c_1~. Trường hợp này không bình luận gì thêm.
• Vì vậy, ta xóa ~b_1~ và ~c_1~ khỏi hai dãy, chuyển về bài toán con với ~2n - 2~ món đồ chơi. Theo nguyên lý quy nạp toán học, ta chứng minh được thuật toán tham lam của ta đã đúng.

Trường hợp 2. ~b_1 < c_1~.

• Thuật toán tham lam sẽ bỏ ~b_1~.
• Trong mọi bộ ghép hợp lệ, chắc chắn không có bộ ghép nào dùng ~b_1~, vì ~b_1 < c_1 < c_j~.
• Như vậy, ta có thể loại hẳn ~b_1~ và ~c_n~. mà không làm giảm kích thước cặp ghép cực đại tối đa. ~M~ sẽ chỉ dùng các món đồ từ ~2~ tới ~n~ của Bờm. Bài toán tiếp tục với ~n - 1~ món đồ mỗi người của Bờm và Cuội.
• Theo nguyên lý quy nạp toán học, ta chứng minh được thuật toán tham lam của ta đã đúng.