# Trò chơi trên lá bài
>Note: Subtask còn khủng hơn cả thuật full.

## 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ó $k (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 \cdot (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í)*.
Từ một hàm `đệ_quy(vector<int> a)` ta gọi đệ quy tới $k(k-1)$ hàm khác.
Phân tích độ phức tạp:
+ Mỗi hàm đệ quy với $a$ có $k$ phần tử sẽ gọi đệ quy tới $k(k-1)$ hàm đệ quy, với những dãy $a'$ có $k-1$ phần tử.
+ Số lần gọi hàm khác nhau là $n(n-1) \times (n-1)(n-2) \times \dots = n!(n-1)!$.
+ Với mỗi cặp lá bài được chọn, tốn chi phí $O(n)$ để xóa đi một lá bài

$\Rightarrow$ Độ phức tạp mỗi test là $O((n!)^2 \times n^3)$.

## Subtask 3

Đặ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 trạng thái `mask`, ta duyệt qua $n^2$ cặp số và xóa đi (/thêm vào) tập hợp `mask` để có được các trạng thái `mask'` liền trước (/tiếp theo).
ĐPT $O(2^n \times n^2)$

## 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 $v$, và giữ lại lá bài $u$, 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ị thu được không có chu trình. Đó là bởi vì khi thêm cung $(u \rightarrow v)$ thì lá bài $v$ đã bị vứt đi, nên sẽ không thể vẽ thêm các cung $v \rightarrow \dots$ nữa. Tổng quát hơn: Bất kì đỉnh $x$ nào mà có tồn tại đỉnh cha thì ta không được thêm bất kì cung nào bắt đầu từ $x$. Khi ta nối $u \rightarrow v$ thì mọi đỉnh $w$ nằm trong cây con gốc $v$ đều **không được** nối ngược lên $u$ (như là $v \rightarrow a \rightarrow b \rightarrow c \rightarrow \dots \rightarrow w$).
+ Tập hợp các cạnh ta chọn tạo thành 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. (nếu không chọn đủ $n-1$ cạnh thì tạo thành một "rừng", tức là nhiều cây khác nhau chứ không phải 1 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 \cdot log_2(n))$, đủ nhanh để chạy cho $T = 100$ test.