Phân tích

Gọi \(p_q\) là xác suất đáp án câu \(q\) là T; \(Q_T,Q_F\) là tập câu ta trả lời T,F. Theo tính tuyến tính của kỳ vọng, cần tối đa

Tuyến tính kỳ vọng dùng được bất kể phụ thuộc có điều kiện phức tạp giữa các câu; dù các câu không độc lập theo nghĩa xác suất, ta vẫn xử lý từng câu riêng. Đây là mẹo quan trọng trong nhiều bài kỳ vọng.

Các lời giải dùng phân số. Số cần thiết có thể vượt \(64\) bit ở Test Set 3 và tùy cài đặt cả Test Set 2. Test Set 2 vẫn có thể làm bằng số nguyên 64-bit, Test Set 3 bằng 128-bit. C/C++ có __int128, Java/C# có BigInteger, JavaScript có BigInt, Bash có bc, Python/Ruby/Haskell có số nguyên dài. Giới hạn không thể giảm nhiều để chỉ dùng 64-bit vì sẽ cho phép lời giải dưới tối ưu vượt Test Set 3.

Có thể có 1 hoặc 2 thí sinh ở hai nhóm đầu, 3 ở nhóm cuối. Không cần xử lý riêng: sao chép một thí sinh với cùng đáp án và điểm tạo trường hợp tương đương, nên luôn giả sử có số thí sinh tối đa.

Test Set 1

Liệt kê \(2^Q\) chuỗi, lọc những chuỗi làm sai điểm bất kỳ thí sinh. Với các chuỗi còn lại, \(p_q\) là tỷ lệ chuỗi trả T ở câu \(q\). Trả T nếu \(p_q>1/2\), F nếu \(p_q<1/2\), tùy ý nếu bằng.

Test Set 2 — lời giải bằng nhận xét

Chia câu hỏi thành loại. Nếu hai câu nhận cùng câu trả lời từ từng thí sinh thì theo đối xứng chúng có cùng \(p_q\). Gọi \(p_{ab}\) là xác suất đáp án T khi hai thí sinh trả \(a,b\). Mọi \(p_q\) là một trong \(p_{TT},p_{TF},p_{FT},p_{FF}\); đối xứng bù cho \(p_{TT}=1-p_{FF}\) và \(p_{TF}=1-p_{FT}\).

Do đó mọi \(p_q\) là hàm tuyến tính của hai ẩn \(p_{TT},p_{TF}\). Điểm kỳ vọng của hai thí sinh cũng tuyến tính theo hai ẩn và phải bằng điểm thực, cho hệ hai phương trình hai ẩn. Giải hệ để có mọi \(p_q\), rồi chọn đáp án xác suất lớn hơn.

Có bốn trường hợp theo việc hai ẩn lớn/nhỏ hơn \(1/2\); bằng \(1/2\) làm các trường hợp tương đương. Bốn trường hợp chính xác là trả giống một trong hai thí sinh hoặc bù của một người. Điểm của đáp án người \(i\) là \(S_i\), điểm đáp án bù là \(Q-S_i\), nên có thể trực tiếp chọn tốt nhất trong bốn, đơn giản hóa cài đặt.

Test Set 2 — lời giải quy hoạch động chuẩn

Với hai thí sinh, định nghĩa \(f(s_1,s_2,q)\) là số cách trả các câu \(q..Q\) sao cho thí sinh 1 đúng đúng \(s_1\) câu và thí sinh 2 đúng \(s_2\) câu:

với \(I_i(q,c)=1\) nếu người \(i\) trả \(c\) ở câu \(q\), ngược lại \(0\). Cơ sở \(f(0,0,Q+1)=1\), và \(f(s_1,s_2,Q+1)=0\) nếu một điểm khác \(0\); có thể trả \(0\) ngay khi điểm âm để dễ memoization.

Ghi nhớ hóa tính hàm trong \(O(Q^3)\). Xác suất câu 1 là T:

Đổi thứ tự để mỗi câu thành câu đầu rồi chạy lại cho mọi xác suất tạo \(O(Q^4)\), hơi chậm. Nhưng các câu có cùng cặp đáp án có cùng xác suất, nên chỉ chạy cho tối đa bốn loại, giảm còn \(O(Q^3)\). Đối xứng bù có thể giảm còn hai loại nhưng không đổi độ phức tạp và không cần.

Test Set 3

Có thể thêm điểm người thứ ba thành một chiều DP, nhưng chiều mới và \(Q\) lớn dễ quá chậm. Kết hợp đầy đủ nhận xét Test Set 2 với vét cạn Test Set 1: có \(8\) biến \(p_{abc}\), các cặp bù có xác suất bù, nên chỉ còn bốn loại. Đánh số loại \(1..4\), có \(q_j\) câu loại \(j\).

Bộ \((t_1,t_2,t_3,t_4)\), \(0\le t_j\le q_j\), biểu diễn chuỗi trả T cho đúng \(t_j\) câu loại \(j\). Nó đại diện cho

chuỗi. Lọc các bộ cho đúng điểm từng thí sinh tương đương liệt kê đáp án phù hợp như Test Set 1; từ đó đếm lựa chọn \(t_j\) xác suất lớn nhất cho từng loại.

Có nhiều nhất \((Q/4)^4\) bộ; độ phức tạp \(O(Q^4)\) nhưng hệ số \(1/256\) đáng kể, cài đặt tốt chạy thoải mái.

Còn có thể cải tiến bằng hệ phương trình. Điểm ba thí sinh là ba hàm tuyến tính của \(t_1,t_2,t_3,t_4\), tạo hệ 3 phương trình 4 ẩn. Chỉ cần thử mọi giá trị của một \(t_j\), rồi giải hệ để xác định duy nhất ba ẩn còn lại; thời gian giảm xuống \(O(Q)\).

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng 1A, bài Hacked Exam.