Subtask 1

\(n \le 5\) nên ta có thể cày trâu. Ta có hàm đệ_quy(vector<int> a), \(a\) là danh sách các chỉ số chưa bị xóa. Giả sử mảng \(a\) có \(1 < k \le n\) phần tử. Tại đây ta xét qua mọi khả năng như đề bài đã chỉ ra : Duyệt qua \(k*(k-1) / 2\) cặp lá bài, với mỗi cặp chọn xóa đi một trong hai lá bài nên có \(2\) khả năng (đương nhiên ta sẽ chọn số nhỏ hơn trong hai số \(R[i] \oplus B[j]\) và \(R[j] \oplus B[i]\) để tính vào chi phí). Do đó từ trạng thái đệ_quy(vector<int> a) ta gọi đệ quy tới \(k * (k-1)\) trạng thái khác. Tổng số trạng thái có thể xét tới chính là \(n! \times (n-1)!\), đủ bé để cày trâu. Độ phức tạp mỗi test là \(O(n! \times (n-1)! \times n^2)\).

Subtask 2

Đặt \(f(mask)\) là chi phí bé nhất trong các cách chọn lá bài để xóa đi tập hợp \(T\) được biểu diễn bởi bitmask mask. Với mỗi bitmask mask, ta duyệt qua \(n^2\) cặp số để xét các trạng thái mask' liền trước (hoặc tiếp theo, tùy cách cài) nên độ phức tạp mỗi test là \(2^n \times n^2\), đủ nhanh để chạy cho \(T = 100\) test.

Subtask 4

Ta cọi mỗi thao tác lựa chọn hai lá bài \((u,v)\), sau đó vứt bỏ đi lá bài \(u\), và giữ lại lá bài \(v\), như là một cạnh có hướng \((u \rightarrow v)\) của đồ thị.

Nhận xét :

• Khi ta tạo đồ thị theo cách trên (thông qua việc chọn một số cạnh), ta thu được một đồ thị không có chu trình. Đó là bởi vì khi thêm cung \((u \rightarrow v)\) thì đỉnh u đã bị "xóa" khỏi đồ thị nên không thể xuất hiện các cung \((w \rightarrow u)\) mà w là con cháu của \(v\).
• Tập hợp các cạnh ta chọn chính là một cây : Mỗi thao tác ta xóa đúng một đỉnh, xóa cho tới khi còn một đỉnh duy nhất. Như vậy có chính xác \(n-1\) cạnh. Kết hợp với điều kiện ở trên ta kết luận được đây là cây.

Như vậy bài toán đưa về : tìm cây khung nhỏ nhất của đồ thị gồm \(n\) đỉnh, và \(n * (n-1)\) cạnh được cho ban đầu. Bằng thuật toán Kruskal, ta thực hiện được điều này trong độ phức tạp thời gian \(O(n^2 * log_2(n))\), đủ nhanh để chạy cho \(T = 100\) test.