Bản đồ Hapmap (Tin học trẻ toàn quốc 2023 – Vòng khu vực miền Trung – Bảng C1)
Đề bài
Bản đồ Hapmap của con người giúp chẩn đoán bệnh và tìm thuốc chữa trị mới. Bài toán dùng hai khái niệm sinh học được đơn giản hóa như sau:
- Một Haplotype $H = (h_1, \dots, h_n)$ là xâu nhị phân độ dài $n$ (mỗi $h_i$ là 0 hoặc 1).
- Một Genotype $G = (g_1, \dots, g_n)$ là xâu độ dài $n$ tạo ra từ hai Haplotype $H$ và $H'$ theo quy tắc: $g_i = 0$ nếu $h_i = h'_i = 0$; $g_i = 1$ nếu $h_i = h'_i = 1$; $g_i = 2$ nếu $h_i \ne h'_i$.
Mỗi cặp $(H, H')$ tạo ra đúng một Genotype, nhưng một Genotype có thể được tạo từ nhiều cặp khác nhau. Các nhà khoa học muốn "giải mã" ngược: với một tập Genotype, tìm một tập ít Haplotype nhất sao cho mỗi Genotype đều tạo được từ hai Haplotype (có thể trùng nhau) trong tập.
Yêu cầu: cho $k$ Genotype $G_1, \dots, G_k$, hãy tìm $k$ cặp $(H_t, H'_t)$ với $(H_t, H'_t)$ tạo ra $G_t$, sao cho tập $\{H_1, H'_1, \dots, H_k, H'_k\}$ có ít phần tử nhất.
Dữ liệu vào: dòng đầu hai số nguyên dương $k, n$ ($k \le 100$, $n \le 200$); $k$ dòng sau, dòng thứ $t$ là xâu độ dài $n$ gồm các ký tự 0, 1, 2 – Genotype $G_t$.
Kết quả: dòng đầu số nguyên dương $p$ – số Haplotype của tập tìm được; $p$ dòng sau, mỗi dòng một xâu nhị phân độ dài $n$. Mỗi Genotype phải tạo được từ hai Haplotype trong tập em in ra. Có nhiều đáp án thì in đáp án bất kỳ.
Cách tính điểm: mỗi test chấm riêng. Gọi $p$ là số Haplotype em tìm được, $r$ là kết quả của Ban giám khảo. Nếu kết quả không hợp lệ hoặc $p > 2k$ thì được 0 điểm; ngược lại được tỉ lệ điểm của test là
$\min\left\{1, \left(\dfrac{r}{p}\right)^3\right\}$.
Subtask: Subtask 1 (50%): $k \le 10$. Subtask 2 (50%): không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.
2 4
1212
11102
1110
1011Giải thích: $G_1 = 1212$ tạo từ cặp $(1110, 1011)$: hai vị trí đầu và thứ ba giống nhau (1, 1), vị trí 2 và 4 khác nhau → ra ký tự 2. $G_2 = 1110$ tạo từ cặp $(1110, 1110)$. Tập Haplotype chỉ có 2 phần tử.
Lời mở đầu
Đây là bài "nặng đô" nhất của đề miền Trung bảng C1: một bài tối ưu – điểm phụ thuộc vào việc tập Haplotype của em nhỏ tới đâu so với của Ban giám khảo. Không có thuật toán nhanh nào cho đáp án tốt nhất, nên lời giải là: biến đổi bài toán cho gọn, nghĩ một cách tham lam hợp lý, rồi dùng hết thời gian để cải thiện dần bằng mô phỏng tôi luyện. Mình đi 3 mức: một cặp riêng cho mỗi Genotype (luôn hợp lệ) → tham lam dùng lại Haplotype → tham lam + mô phỏng tôi luyện (lời giải mình đã nộp tinhoctre.vn được 100 điểm).
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test có gì?
Bộ test trên CLUE gồm 20 test (test 1 là ví dụ của đề): test 1–10 có $k \le 10$ (subtask 1), test 11–20 có $k = 100$. Phần lớn test được sinh "có gieo": tạo trước một số Haplotype ẩn rồi ghép ngẫu nhiên từng cặp thành Genotype – đúng như câu chuyện của đề; một số test có Genotype hoàn toàn ngẫu nhiên (khó dùng chung), test có $n = 200$ toàn ký tự 2, test có Genotype trùng nhau.
| Test | $k$ | $n$ | Genotype khác nhau | Số ký tự 2 nhiều nhất | $r$ (file đáp án) |
|---|---|---|---|---|---|
| 1 | 2 | 4 | 2 | 2 | 2 |
| 2 | 1 | 1 | 1 | 1 | 2 |
| 3 | 4 | 4 | 3 | 0 | 3 |
| 4 | 10 | 200 | 6 | 100 | 4 |
| 5 | 10 | 50 | 8 | 28 | 6 |
| 6 | 10 | 8 | 10 | 6 | 7 |
| 7 | 10 | 200 | 10 | 69 | 20 |
| 8 | 10 | 6 | 10 | 5 | 11 |
| 9 | 10 | 120 | 8 | 16 | 5 |
| 10 | 10 | 200 | 7 | 200 | 6 |
| 11 | 100 | 200 | 75 | 117 | 20 |
| 12 | 100 | 200 | 94 | 122 | 49 |
| 13 | 100 | 200 | 100 | 117 | 85 |
| 14 | 100 | 30 | 94 | 23 | 40 |
| 15 | 100 | 12 | 100 | 10 | 57 |
| 16 | 100 | 200 | 95 | 124 | 40 |
| 17 | 100 | 150 | 85 | 54 | 30 |
| 18 | 100 | 200 | 100 | 56 | 200 |
| 19 | 100 | 10 | 100 | 7 | 101 |
| 20 | 100 | 200 | 80 | 113 | 65 |
Cột $r$ là số dòng đầu của file đáp án – kết quả của lời giải cách 3 (chạy một lần, mình đã thử chạy lâu hơn với nhiều hạt giống ngẫu nhiên nhưng không tốt hơn ở test nào). Với các test "có gieo", $r$ không vượt số Haplotype ẩn thật sự được dùng.
Điểm (chấm bằng checker, quy về thang 100) của các cách bên dưới theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 | Cách 2 | Cách 3 (TB 3 lần) |
|---|---|---|---|---|---|
| Subtask 1 (50%) | $k \le 10$ | 1–10 | 19,72 | 35,90 | 50,00 |
| Subtask 2 (50%) | $k \le 100$ | 11–20 | 7,45 | 17,12 | 49,95 |
| Tổng | 1–20 | 27,17 | 53,02 | 99,95 |
Ý tưởngChỉ cần chọn một Haplotype cho mỗi Genotype
Nhận xét 1. Nhìn một Genotype $G$: ở vị trí $g_i = 0$ hoặc $1$, cả $H$ và $H'$ bắt buộc bằng $g_i$. Chỉ ở vị trí $g_i = 2$ mới có lựa chọn, và ở đó $H'$ luôn là đảo bit của $H$. Vậy:
- $H$ phải khớp $G$: ở mọi vị trí không phải 2, $h_i = g_i$;
- khi đã chọn $H$ thì $H'$ được xác định luôn: $H' = H \oplus m$, với $m$ là mặt nạ các vị trí 2 (đảo các bit đó). Mình gọi $H'$ là "bạn đôi" của $H$ đối với $G$.
Như vậy bài toán trở thành: với mỗi Genotype $G_t$ chọn một Haplotype $h_t$ khớp nó; tập kết quả là hợp của các cặp $\{h_t, h_t \oplus m_t\}$; cần ít phần tử phân biệt nhất. Genotype có $c$ ký tự 2 có $2^c$ lựa chọn (mỗi cặp được đếm 2 lần), nên vét cạn chỉ làm nổi với dữ liệu tí hon.
Nhận xét 2 (tham lam). Một Genotype "rẻ" nhất khi cả $h_t$ và bạn đôi của nó đã có sẵn trong tập (thêm 0 Haplotype mới); kế đến là $h_t$ đã có, chỉ thêm bạn đôi (thêm 1). Xử lý Genotype ít ký tự 2 trước (chúng gần như bị ép buộc, như $1110$ chỉ có một cách), rồi các Genotype sau cố "dùng lại" Haplotype đã có.
Em nhập các Genotype rồi bấm Tiếp để xem cách tham lam dùng lại Haplotype (ô vàng là các vị trí 2, xanh lá = Haplotype dùng lại, xanh dương = Haplotype thêm mới):
Cách 1Mỗi Genotype một cặp riêng (luôn hợp lệ)
Cách dễ nhất: với mỗi Genotype, $H$ lấy 0 ở mọi vị trí 2, $H'$ lấy 1 ở mọi vị trí 2. Cho tất cả vào một set để bỏ trùng. Kết quả luôn hợp lệ và $p \le 2k$ nên chắc chắn có điểm, nhưng thường gấp đôi $r$.
Kết quả chạy thật (chấm bằng checker): cả hai bản đều hợp lệ ở 20/20 test, tổng điểm 27,17/100. Dữ liệu được sinh từ ít Haplotype ẩn nên "cặp 0/1 cố định" gần như không bao giờ trùng nhau giữa các Genotype.
Cách 2Tham lam: dùng lại Haplotype đã có
Làm đúng như nhận xét 2: bỏ Genotype trùng, sắp theo số ký tự 2 tăng dần. Với mỗi Genotype, duyệt các Haplotype $h$ đang có trong tập: nếu $h$ khớp thì "giá" là 0 khi bạn đôi của $h$ cũng có sẵn, ngược lại là 1. Chọn $h$ có giá nhỏ nhất; nếu không có $h$ nào khớp thì tự tạo (vị trí 2 lấy 0) và thêm cả cặp.
khop(g, h): kiểm tra mọi vị trí không phải 2.banDoi(g, h): đảo bit của $h$ ở các vị trí 2.tot= số Haplotype phải thêm mới (0, 1, hoặc 3 = chưa tìm được). Gặp giá 0 thì dừng duyệt luôn.stable_sortvới hàm so sánh đếm số ký tự 2: Genotype bị ép buộc nhiều được xử lý trước.
Kết quả chạy thật: hợp lệ 20/20 test, tổng 53,02/100 (bản Python cho đúng y kết quả). Ăn trọn những test nhỏ, nhưng ở test $k = 100$ tham lam "chọn ngay" thường kẹt: một quyết định sớm (chọn $h$ tình cờ khớp) làm các Genotype sau không dùng chung được nữa.
Cách 3Tham lam + mô phỏng tôi luyện (100 điểm)
Cách 2 cho một lời giải ban đầu khá ổn; ta sửa dần nó bằng mô phỏng tôi luyện (simulated annealing): lặp liên tục, mỗi lần thử thay đổi lựa chọn $h_t$ của một Genotype ngẫu nhiên, tính lại số Haplotype phân biệt; nếu tốt hơn hoặc bằng thì nhận, nếu tệ hơn $d$ thì vẫn nhận với xác suất $e^{-d / temp}$ (nhiệt độ $temp$ giảm dần từ 0,6 xuống 0,02 theo thời gian) để thoát khỏi "cực tiểu địa phương". Ba kiểu thay đổi:
- Chia sẻ: lấy một Haplotype của Genotype khác, "chiếu" nó lên $G_t$ (giữ bit ở vị trí 2 của $G_t$, các vị trí còn lại lấy theo $G_t$) làm $h_t$ mới.
- Gộp: chọn $G_s$ tương thích với $G_t$ (không có vị trí cố định nào mâu thuẫn), ép hai Genotype dùng chung một Haplotype.
- Lật bit: đảo một bit ngẫu nhiên ở vị trí 2 của $h_t$.
Để mỗi bước thật nhanh: Haplotype lưu thành 4 số unsigned long long (256 bit ≥ 200), "khớp" và "bạn đôi" chỉ là vài phép AND/OR/XOR; số Haplotype phân biệt đếm bằng unordered_map (mỗi Haplotype đang được bao nhiêu Genotype dùng) nên thay đổi một Genotype chỉ tốn $O(1)$ thao tác trên bảng băm. Trong 0,75 giây chạy được vài triệu bước; luôn lưu lại trạng thái tốt nhất từng gặp.
proj(t, u)= $(u \;\&\; m_t) \;|\; v_t$: "chiếu" $u$ lên $G_t$.compatible(t, u): $u$ khớp $G_t$ (các vị trí cố định của $u$ đúng bằng $G_t$).setChoice(t, h): gỡ cặp cũ của $G_t$ khỏi bảng đếm, thêm cặp mới.distinctCntluôn là số Haplotype phân biệt hiện tại.- Bước khởi tạo giống cách 2 nhưng khi không dùng lại được, các bit ở vị trí 2 được lấy theo một Genotype tương thích chưa xử lý (để sau này Genotype đó dễ dùng lại).
- Thời gian đo bằng
clock()(thời gian CPU), dừng ở 0,75 giây để an toàn với giới hạn 1 giây.
Kết quả chạy thật (3 lần): hợp lệ 20/20 test, tổng điểm 100,00 / 100,00 / 99,85 /100, chạy lâu nhất 0,76 giây. Chi tiết từng test:
| Test | $r$ | Cách 1 $p$ | điểm | Cách 2 $p$ | điểm | Cách 3 (3 lần chạy) $p$ | điểm TB |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 0,296 | 2 | 1,000 | 2 / 2 / 2 | 1,000 |
| 2 | 2 | 2 | 1,000 | 2 | 1,000 | 2 / 2 / 2 | 1,000 |
| 3 | 3 | 3 | 1,000 | 3 | 1,000 | 3 / 3 / 3 | 1,000 |
| 4 | 4 | 10 | 0,064 | 4 | 1,000 | 4 / 4 / 4 | 1,000 |
| 5 | 6 | 16 | 0,053 | 16 | 0,053 | 6 / 6 / 6 | 1,000 |
| 6 | 7 | 17 | 0,070 | 11 | 0,258 | 7 / 7 / 7 | 1,000 |
| 7 | 20 | 20 | 1,000 | 20 | 1,000 | 20 / 20 / 20 | 1,000 |
| 8 | 11 | 16 | 0,325 | 12 | 0,770 | 11 / 11 / 11 | 1,000 |
| 9 | 5 | 13 | 0,057 | 5 | 1,000 | 5 / 5 / 5 | 1,000 |
| 10 | 6 | 14 | 0,079 | 13 | 0,098 | 6 / 6 / 6 | 1,000 |
| 11 | 20 | 144 | 0,003 | 24 | 0,579 | 20 / 20 / 20 | 1,000 |
| 12 | 49 | 187 | 0,018 | 161 | 0,028 | 49 / 49 / 49 | 1,000 |
| 13 | 85 | 199 | 0,078 | 191 | 0,088 | 85 / 85 / 85 | 1,000 |
| 14 | 40 | 188 | 0,010 | 168 | 0,013 | 40 / 40 / 40 | 1,000 |
| 15 | 57 | 166 | 0,040 | 111 | 0,135 | 57 / 57 / 57 | 1,000 |
| 16 | 40 | 188 | 0,010 | 103 | 0,059 | 40 / 40 / 40 | 1,000 |
| 17 | 30 | 166 | 0,006 | 57 | 0,146 | 30 / 30 / 30 | 1,000 |
| 18 | 200 | 200 | 1,000 | 200 | 1,000 | 200 / 200 / 200 | 1,000 |
| 19 | 101 | 161 | 0,247 | 124 | 0,540 | 101 / 101 / 102 | 0,990 |
| 20 | 65 | 151 | 0,080 | 69 | 0,836 | 65 / 65 / 65 | 1,000 |
Khung chạy tay bên dưới mô phỏng phần đọc dữ liệu + khởi tạo tham lam (phần mô phỏng tôi luyện chạy hàng triệu bước ngẫu nhiên nên chỉ được tóm tắt trong một bước). Mình chọn các dữ liệu mẫu mà khởi tạo đã đạt tối ưu, nên kết quả in ra đúng y chương trình thật.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Điểm trên bộ test (/100) | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Mỗi Genotype một cặp riêng | C++ | 27,17 | 0.005s | Luôn hợp lệ, nhưng gần như không dùng chung được gì |
| 1. Mỗi Genotype một cặp riêng | Python | 27,17 | 0.028s | Như bản C++ |
| 2. Tham lam: dùng lại Haplotype đã có | C++ | 53,02 | 0.004s | Tất định, rất nhanh |
| 2. Tham lam: dùng lại Haplotype đã có | Python | 53,02 | 0.026s | Như bản C++ |
| 3. Tham lam + mô phỏng tôi luyện | C++ | 100,00 / 100,00 / 99,85 | 0.758s | 3 lần chạy; dừng theo đồng hồ nên kết quả có thể lệch nhẹ giữa các lần |