Chu kỳ một giây

Nhận xét đầu tiên là mọi laser quay cùng tốc độ. Sau mỗi giây, bất kể chiều quay, tất cả laser lại trở về đúng cấu hình đầu vào; mỗi giây sau chỉ lặp lại giây trước. Vì vậy, giả sử ảnh đầu vào ứng với thời điểm \(t=0\) và chỉ xét \(0\le t\le1\).

Test Set 1: thử mọi chiều quay

Vì số laser rất nhỏ, ta thử mọi tổ hợp chiều quay. Với mỗi tổ hợp khiến đoạn chuẩn có lúc không được che phủ, cộng \(2^{-N}\) vào đáp án.

Khi đã cố định các chiều quay, ánh xạ mỗi laser thành khoảng thời gian mà nó chạm đoạn chuẩn, rồi kiểm tra hợp các khoảng có phủ trọn một giây hay không. Các khoảng nằm trên vòng tròn thời gian modulo 1: một khoảng có thể bắt đầu tại \(t_0\) và kết thúc tại \(t_1<t_0\), khi ấy nó phủ từ \(t_0\) đến 1 và từ 0 đến \(t_1\). Ta có thể tách mỗi khoảng quấn qua 0 thành hai khoảng thường, sắp tăng theo đầu trái, đặt \(t=0\), rồi xét từng \((t_0,t_1)\). Nếu \(t_0>t\) thì có một lỗ hổng; nếu không, cập nhật \(t=\max(t,t_1)\). Sau cùng có lỗ hổng khi và chỉ khi \(t<1\).

Với laser có đầu mút \(p\) và điểm thứ hai \(q\), hai biên của khoảng che phủ được suy ra từ các góc \(qp(0,0)\) và \(qp(0,1000)\), rồi chia cho \(2\pi\). Tính trực tiếp bằng số thực rất dễ gặp lỗi chính xác. Có thể chỉ dùng số nguyên bằng cách giữ các thời điểm dưới dạng ký hiệu là các góc của những vectơ ban đầu và so sánh bằng tích có hướng. Phần trình bày dưới đây coi như đã có các thời điểm thực, nhưng mọi phép toán cần thiết đều cài được trên biểu diễn gián tiếp ấy.

Có \(2^N\) tổ hợp và mỗi tổ hợp cần duyệt \(N\) laser, nên độ phức tạp là \(O(N2^N)\), đủ cho Test Set 1.

Test Set 2: đối xứng của các khoảng

Hai khoảng ứng với hai chiều quay của cùng một laser đối xứng nhau: chúng có dạng \((t_0,t_1)\) và \((1-t_1,1-t_0)\). Trên vòng thời gian, đây vừa là đối xứng qua \(1/2\) vừa là đối xứng qua điểm \(0=1\). Vì mỗi khoảng ngắn hơn \(1/2\), một cặp chỉ có thể thuộc một trong ba loại:

1. Hai khoảng rời nhau, một nằm trong \((0,1/2)\) và một trong \((1/2,1)\), chẳng hạn \([0.2,0.3]\) và \([0.7,0.8]\).
2. Hai khoảng chồng nhau quanh \(1/2\), chẳng hạn \([0.3,0.6]\) và \([0.4,0.7]\).
3. Hai khoảng chồng nhau quanh \(0\), cũng là quanh \(1\), chẳng hạn \([0.8,0.1]\) và \([0.9,0.2]\).

Ở hai loại cuối, phần giao là thời gian chắc chắn được bảo vệ dù laser quay theo chiều nào, nên có thể loại phần đó khỏi miền cần xét và chỉ giữ hiệu đối xứng của hai khoảng. Ví dụ với \([0.3,0.6]\) và \([0.4,0.7]\), ta bỏ \([0.4,0.6]\), giữ \([0.3,0.4]\) và \([0.6,0.7]\). Làm như vậy cho mọi laser, phần còn phải xét là một khoảng con \(u_1\) của \((0,1/2)\) và khoảng con đối xứng \(u_2\) của \((1/2,1)\); mỗi laser cung cấp đúng hai khoảng đối xứng, mỗi phía một khoảng.

Bài toán trở thành: với các cặp \((a,b)\) và \((1-b,1-a)\), xác suất để việc chọn ngẫu nhiên đồng đều một khoảng từ mỗi cặp không phủ đồng thời cả \(u_1\) lẫn \(u_2\) là bao nhiêu? Do đối xứng, một cách chia các khoảng phủ \(u_1\) khi và chỉ khi cách chia đối nghịch phủ \(u_2\). Tương đương, chỉ lấy danh sách các khoảng nằm trong \(u_1\) và chia ngẫu nhiên chúng thành hai phía; cần xác suất có ít nhất một phía không phủ hết \(u_1\).

Quy hoạch động

Sắp các khoảng theo đầu trái không giảm. Nếu \(u_1=(v,w)\), định nghĩa \(f(i,x,y)\) là xác suất rằng khi chia các khoảng \(i,i+1,\ldots,N\), không phải cả hai phần còn lại \((x,w)\) và \((y,w)\) đều được phủ. Nói cách khác, các khoảng \(1,\ldots,i-1\) đã được chia sao cho hai phía phủ liên tục lần lượt \((v,x)\) và \((v,y)\).

• Nếu \(\min(x,y)\ge w\) thì cả hai phía đã phủ hết, nên \(f(i,x,y)=0\).
• Nếu \(i>N\), hoặc đầu trái \(a_i>\min(x,y)\), ít nhất một phía chắc chắn có lỗ, nên \(f(i,x,y)=1\).
• Với khoảng thứ \(i\) là \((a,b)\) trong các trường hợp còn lại,

Đáp án là \(f(1,v,v)\).

\(x,y\) chỉ có thể là \(v\) hoặc đầu phải của một khoảng, cho cận ban đầu \(O(N^3)\). Hơn nữa, \(\max(x,y)\) luôn bằng giá trị lớn nhất giữa \(v\) và các đầu phải đã gặp, nên số trạng thái và thời gian giảm xuống \(O(N^2)\).

Ta còn cần một tối ưu nữa. Nếu \(\min(x,y)\) không nằm trong \(K\) đầu phải lớn nhất đã thấy, đóng góp của \(f(i,x,y)\) vào đáp án cuối bị nhân với không quá \(2^{-K}\). Với \(K\) khoảng 50, ảnh hưởng này nhỏ đến mức không đáng kể so với sai số cho phép; có thể xấp xỉ trạng thái đó bằng 0. Khi ấy chỉ còn \(O(KN)\) trạng thái cần tính.

Cách đệ quy có nhớ khá khó cài nếu muốn dùng chỉ số nguyên thay cho số thực. Một cách tiến đơn giản hơn là giữ từ điển state -> probability, trong đó trạng thái \((x,y)\) luôn được sắp để \(x\le y\). Ban đầu chỉ có {(v,v): 1}. Với mỗi \((a,b)\) và mỗi trạng thái \((s_1,s_2)\) có xác suất \(p\):

• nếu \(a>s_1\), cộng toàn bộ \(p\) vào đáp án vì trạng thái này chắc chắn để lại thời gian không được canh gác;
• nếu không, cộng \(p/2\) vào hai trạng thái sort(max(s1,b),s2) và sort(s1,max(s2,b)).

Đó là phiên bản lặp của thuật toán bậc hai. Để đạt gần tuyến tính, chỉ cần bỏ trạng thái có xác suất quá nhỏ, tức là không làm gì khi \(p<\varepsilon\). Số trạng thái giữ lại mỗi bước được chặn bởi \(K\), nên thời gian \(O(KN)\) và có thể dùng hai lớp từ điển với bộ nhớ \(O(K)\).

Dựa trên phân tích chính thức của Google Code Jam 2018, Chung kết thế giới, bài The Cartesian Job.