Hướng dẫn cho Google Code Jam 2012 - Upstairs/Downstairs

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Phân tích: Upstairs/Downstairs

Upstairs/Downstairs được thêm vào vòng Chung kết vào phút chót, thay một đề xuất đã có từ một năm trước nhưng xuất hiện ở cuộc thi khác hai tháng trước đó. Bài toán phỏng theo một trải nghiệm của tác giả trong kỳ nghỉ; khi ấy ông ở tầng dưới.

Lời giải gồm hai quan sát và một thuật toán. Trước hết viết công thức cho đại lượng cần tối thiểu hóa. Gọi \(p_i\) là xác suất hoạt động thứ \(i\) của Konstantin làm Ilia thức:

\[ \begin{aligned} P(\text{bị đánh thức})={}&(1-p_0)\left(1-(1-p_1)(1-p_2)\cdots(1-p_K)\right)\\ &+p_0(1-p_1)\left(1-(1-p_2)(1-p_3)\cdots(1-p_K)\right)\\ &+p_0p_1(1-p_2)\left(1-(1-p_3)(1-p_4)\cdots(1-p_K)\right)+\cdots. \end{aligned} \]

Quan sát 1: Hoạt động ồn ào trước

Ta tìm lý do nên làm hoạt động ồn hay yên tĩnh trước. Trực giác nói hoạt động ồn nên trước: giữ Ilia thức rồi cố giữ anh ấy ngủ có vẻ hợp lý.

Trong công thức, các số hạng thay đổi khi hoán đổi \(p_i\) và \(p_{i+1}\) là

\[ \begin{aligned} &p_0p_1\cdots p_{i-1}(1-p_i)\left(1-(1-p_{i+1})(1-p_{i+2})\cdots(1-p_K)\right)\\ &+p_0p_1\cdots p_{i-1}p_i(1-p_{i+1})\left(1-(1-p_{i+2})\cdots(1-p_K)\right). \end{aligned} \]

Rút gọn hai số hạng:

\[ \begin{aligned} &p_0\cdots p_{i-1}\big[(1-p_i)+p_i(1-p_{i+1})\\ &\qquad-(1-p_i)(1-p_{i+1})\cdots(1-p_K)-p_i(1-p_{i+1})\cdots(1-p_K)\big]\\ ={}&p_0\cdots p_{i-1}\big[1-p_ip_{i+1}-(1-p_{i+1})(1-p_{i+2})\cdots(1-p_K)\big]. \end{aligned} \]

Đại lượng này nhỏ nhất khi chọn \(p_{i+1}<p_i\), xác nhận hoạt động ồn hơn nên xảy ra trước. Liên tục hoán đổi các cặp kề nhau cho thấy trong lời giải tối ưu, hoạt động được thực hiện từ ồn nhất đến yên tĩnh nhất.

Quan sát 2: Chọn cực trị

Công thức ban đầu của \(P(\text{bị đánh thức})\) là hàm tuyến tính theo từng \(p_i\). Vì thế theo mỗi \(p_i\), giá trị nhỏ nhất đạt tại giá trị lớn nhất hoặc nhỏ nhất được phép.

Kết hợp hai quan sát: Konstantin nên thực hiện trước \(K-q\) hoạt động ồn nhất, theo thứ tự từ ồn đến yên, rồi thực hiện \(q\) hoạt động yên tĩnh nhất, cũng theo thứ tự từ ồn đến yên. Gọi nhóm đầu là tiền tố, nhóm sau là hậu tố. Một loại hoạt động lặp được \(c\) lần được xem là \(c\) hoạt động riêng biệt.

Các thuật toán khả dĩ

Với Small, thử mọi \(q\). Có \(O(K)\) giá trị, và tính ngây thơ mỗi giá trị tốn \(O(\sum c_i)\), nên tổng thời gian \(O((\sum c_i)^2)\).

Với mỗi hậu tố, chỉ cần theo dõi hai số: xác suất cuối cùng Ilia bị đánh thức nếu bắt đầu hậu tố trong trạng thái thức, và xác suất đó nếu bắt đầu trong trạng thái ngủ. Tiền xử lý hai giá trị cho mỗi trong \(K\) hậu tố trong \(O(K)\); mô phỏng mọi tiền tố cũng trong tổng \(O(K)\) và tra nhanh hậu tố tương ứng. Một chút biến đổi cho đáp án trong \(O(\sum c_i)\).

Một thuật toán tương đương biểu diễn ba trạng thái của Ilia—thức, ngủ, và đã bị đánh thức—bằng vector \(3\times1\), rồi dùng ma trận. Với hoạt động có xác suất \(p\), ma trận chuyển là:

[[p    0    0]
 [1-p  1-p  0]
 [0    p    1]]

Trạng thái ban đầu:

[1
 0
 0]

Ma trận cho một dãy hoạt động là tích các ma trận, với hoạt động ồn nhất nằm bên phải. Ta tính ma trận \(3\times3\) cho mọi tiền tố dài đến \(K\) và mọi hậu tố dài đến \(K\) trong \(O(K)\). Kiểm tra một cặp tiền tố/hậu tố mất \(O(1)\): nhân hai ma trận với nhau rồi nhân vector ban đầu. Tổng thời gian vẫn là \(O(\sum c_i)\). Hai phần tử được in đậm trong ma trận gốc chính là hai xác suất cần theo dõi cho mỗi hậu tố ở thuật toán trước.

Tìm kiếm tam phân đã qua dữ liệu kiểm thử, nhưng...

Vì bài được chuẩn bị phút chót, đến lúc thi ban ra đề mới tự hỏi tìm kiếm tam phân có chọn được \(q\)—độ dài hậu tố—hay không. Kết luận nào cũng chấp nhận được, nhưng nếu không thì đáng lẽ dữ liệu phải có test phá nó.

Câu trả lời là không, nhưng không test sẵn có nào phá được bất kỳ cách tìm kiếm tam phân nào ban ra đề tìm thấy. Vì thế một số thí sinh—đáng chú ý là misof, người đứng thứ ba một phần nhờ điểm bài này—đã nộp lời giải tìm kiếm tam phân và qua toàn bộ dữ liệu.

Trong Code Jam, đôi khi thí sinh nghĩ ra thuật toán không đúng tổng quát theo giới hạn nhưng lại đúng trên dữ liệu kiểm thử. Ban ra đề cố tránh nhưng việc đó vẫn xảy ra. Hệ quả ở đây không đáng kể: cài tìm kiếm tam phân khó ngang, thậm chí hơn lời giải đúng; phần khó của bài đã được giải quyết; và nếu tìm được phản ví dụ, nó sẽ được đặt cả trong Small lẫn Large. Người dùng tam phân sẽ thấy sai từ Small và sửa. misof cũng hơn người thứ tư rất nhiều thời gian, nên top ba có lẽ không đổi.

Vì sao tìm kiếm tam phân thất bại

Tìm kiếm tam phân có vẻ hợp lý. Hàm \(P(\text{bị đánh thức})\) theo \(q\) thực sự giảm nghiêm ngặt rồi tăng nghiêm ngặt nếu bỏ qua các đoạn bằng nhau; chính xác hơn, nó không tăng rồi không giảm. Như vậy chưa đủ: tìm kiếm tam phân cần hàm giảm nghiêm ngặt rồi tăng nghiêm ngặt, nếu không một đoạn hằng dài khiến nó không biết nên đi hướng nào.

Phản ví dụ về nguyên tắc, đồng thời phá một số bài nộp thực tế:

Đáp án đúng:

Case #1: 0.863976521
Case #2: 0.863976521

Ở test đầu, tốt nhất không thực hiện các hoạt động xác suất 1/2. Nhưng vì chúng nằm tận đầu danh sách và bị các hoạt động 1/100 áp đảo về số lượng, tìm kiếm tam phân chuẩn không thấy khác biệt giữa hai độ dài hậu tố nó thử: nó chỉ chuyển một số hoạt động 1/100 từ tiền tố sang hậu tố, còn toàn bộ hoạt động 1/2 vẫn giữ nguyên. Test thứ hai giống hệt nhưng thay 1/100 bằng 99/100, nhằm phá cách tam phân tình cờ chọn đúng hướng ở test đầu.

Paweł i Gaweł

Trong bữa tối sau vòng Chung kết, vài thí sinh Ba Lan rất ngạc nhiên khi biết bài không dựa trên bài thơ Paweł i Gaweł. Sự giống nhau hoàn toàn ngẫu nhiên; lẽ ra họ phải biết điều đó, vì Gaweł—người theo Google Translate là “nghĩ ra những trò nô đùa hoang dã nhất”—sống ở tầng dưới. Nhìn lại, ban ra đề ước đã đặt tên bài theo bài thơ ấy, và có lẽ để Gaweł tối thiểu hóa xác suất Paweł đi câu cá.

Dựa trên phân tích chính thức của Google Code Jam.

Bình luận

Tải bình luận...

Không có bình luận nào.