Một bài toán khác thường

Các bài chỉ có Small khá hiếm trong Code Jam. Đôi khi, như Proper Shuffle của Round 1A 2014, nguyên nhân là lời giải mong đợi dùng ngẫu nhiên và ban tổ chức muốn thí sinh có thể thử lại khi cần, dù xác suất lời giải tối ưu thất bại do may rủi rất nhỏ. Forest University chỉ có Small vì cả hai lý do ấy. Có thể thêm một bộ Small nữa đủ nhỏ để giải chính xác bằng quy hoạch động, nhưng điều đó không giúp phân loại tốt hơn 26 thí sinh đi tiếp.

Với tới 100 môn, số thứ tự học quá lớn để liệt kê. Sai số cho phép rộng bất thường, nên mô phỏng Monte Carlo là lựa chọn tự nhiên: sinh các lịch học và kiểm tra chúng có chứa các chuỗi con cần tìm hay không. Tuy nhiên, điểm khó của bài mô phỏng này lại là làm đúng ngay cả một lần: làm sao lấy mẫu đều từ tập mọi thứ tự môn hợp lệ?

Lấy mẫu có trọng số

Phân tích một khu rừng nhỏ cho ta một quy tắc đơn giản. Xét năm môn A, B, C, D, E; A và E là cơ bản, A là tiên quyết của B và D, còn B là tiên quyết của C.

Có 15 thứ tự: ABCDE, ABCED, ABDCE, ABDEC, ABECD, ABEDC, ADBCE, ADBEC, ADEBC, AEBCD, AEBDC, AEDBC, EABCD, EABDC, EADBC. Trong số đó, \(4/5\) bắt đầu bằng A và \(1/5\) bắt đầu bằng E. Cây gốc A có tổng cộng 4 hậu duệ nếu tính cả A, còn cây gốc E có 1. Đây không phải trùng hợp: khi xây chuỗi môn, hãy chọn trong các môn đang sẵn sàng với xác suất tỉ lệ kích thước cây con của môn đó, tính cả chính nó.

Trong ví dụ, lúc đầu chỉ chọn được A hoặc E, với xác suất \(4/5\) và \(1/5\). Giả sử chọn A. Lựa chọn tiếp theo là B, D, E, có kích thước cây con lần lượt 2, 1, 1, nên xác suất là \(2/4\), \(1/4\), \(1/4\). Giả sử chọn D; lúc này chọn B hoặc E với xác suất \(2/3\) và \(1/3\). Tiếp tục cho đến khi có đủ một thứ tự.

Để chứng minh, thêm một gốc giả làm cha của mọi môn không có tiên quyết. Với cây con gốc \(V\) kích thước \(S\), trước hết sinh đệ quy một lịch cho mỗi cây con của các con \(V\). Đặt \(V\) đầu tiên, rồi chọn đều một cách phân \(S-1\) vị trí còn lại cho các cây con, mỗi cây nhận đúng số vị trí bằng kích thước của nó. Cuối cùng chép thứ tự của từng cây con vào các vị trí đã cấp. Cách dựng này tạo một lịch chọn đều.

Vì ta chọn đều cách phân vị trí rồi xen kẽ đều các cây con, tỉ lệ một môn cấp cao xuất hiện trước có thể suy ra bằng hệ số đa thức. Với hai cây kích thước \(A,B\), có

cách xen kẽ. Số cách bắt đầu bằng phần tử cây A là \((A+B-1)!/((A-1)!B!)\), còn số cách bắt đầu bằng cây B là \((A+B-1)!/(A!(B-1)!)\). Tỉ số của chúng rút gọn thành \(A/B\), giải thích vì sao lấy mẫu tỉ lệ với kích thước cây con là đủ.

Một cách thanh lịch bất ngờ

Sinh một thứ tự ngẫu nhiên tương đương với gán các số phân biệt từ 1 đến \(N\) cho các nút sao cho số của một nút nhỏ hơn số của mọi hậu duệ. Bắt đầu bằng một trong \(N!\) phép gán bất kỳ, chọn đều. Duyệt các nút từ trên xuống; nếu một nút không mang số nhỏ nhất trong cây con của nó, đổi số của nút ấy với số nhỏ nhất.

Kết quả phân bố đều vì mỗi thứ tự cuối có đúng

hoán vị ban đầu ánh xạ tới nó. Khi nút \(X\) sẵn sàng, xác suất nó nhận số nhỏ nhất tỉ lệ với kích thước cây do nó làm gốc, bởi bất kỳ nút nào trong cây ấy nhận số nhỏ nhất cũng sẽ “trao” số đó cho \(X\).

Độ chính xác có đủ không?

Nếu kiểm tra \(K\) chuỗi sinh đều và xác suất thật của một chuỗi con là \(p\), tỉ lệ mẫu chứa nó tuân theo phân phối nhị thức với tham số \(K,p\). Ta có thể xấp xỉ bằng phân phối chuẩn với trung bình \(p\) và độ lệch chuẩn

Với 10000 lần lặp, giá trị này không quá \(0.5/100=5\times10^{-3}\). Sai số cho phép \(3\times10^{-2}\) tương đương sáu độ lệch chuẩn. Xác suất một đáp án cụ thể sai xấp xỉ 1 trên 500 triệu; do có nhiều nhất 500 đáp án cần in, xác suất ít nhất một đáp án sai không quá khoảng 1 trên một triệu.

Giới hạn sai số đủ rộng để một cài đặt nhanh giải được bài ngay cả bằng ngôn ngữ chậm như Python.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2016, Vòng 3.