Phân tích: Hall of Mirrors

Để giữ cho mọi thứ thú vị, chúng tôi đã kết thúc vòng loại với Hall of Mirrors: một bài toán thực sự đầy thử thách. Rất khó để biết bắt đầu từ đâu, và thậm chí còn khó hơn để cài đặt đúng!

Cách hiểu về gương

Bước đầu tiên để giải bài toán này là giảm tập hợp tất cả các góc tia sáng xuống một thứ gì đó mà bạn thực sự có thể kiểm tra. Và để làm được điều đó, việc sử dụng một mẹo nổi tiếng khi suy nghĩ về gương là rất hữu ích. Hãy nhìn vào hai sơ đồ bên dưới. Bạn có thấy tại sao chúng thực sự minh họa cùng một thứ không?

Trong hình bên trái, có một tia sáng trong một căn phòng \(2 \times 1\) phản xạ qua ba tấm gương, và sau đó kết thúc tại nơi nó bắt đầu. Hãy tập trung vào nơi tia sáng phản xạ ở gương phía dưới. Thay vì vẽ tia sáng phản xạ, hãy lấy toàn bộ căn phòng và vẽ nó phản chiếu qua tấm gương này. Sau đó, chúng ta có thể vẽ phần còn lại của đường đi của tia sáng trong hình này. Điều này được minh họa trong sơ đồ bên trái phía dưới:

Tiếp theo, khi tia sáng chạm vào gương bên phải, chúng ta lại có thể vẽ toàn bộ căn phòng phản chiếu qua gương đó, rồi tiếp tục vẽ phần còn lại của đường đi ở đó. Cuối cùng, chúng ta có thể làm điều tương tự cho một tấm gương còn lại để có được bức tranh ban đầu từ phía trên. Cách vẽ này có hai tính chất rất tốt cho chúng ta:

• Tia sáng hoàn toàn thẳng, nó không bao giờ bị bẻ cong hay đổi hướng.
• Bất kể chúng ta thực hiện bao nhiêu lần phản chiếu, và bất kể chúng ở đâu, vị trí phản chiếu của điểm bắt đầu của bạn sẽ luôn nằm ở giữa một ô vuông nào đó.

Cùng với nhau, những điều này gợi ý một sự thật quan trọng mà bạn cần để bắt đầu: để một tia sáng có cơ hội phản xạ lại bạn trong khoảng cách tối đa \(D\), nó phải hướng về tâm của một ô vuông cách bạn một khoảng tối đa \(D\).

Tập test 1 (Small)

Nếu bạn đi được đến đây, bạn có thể thử giải chỉ tập test nhỏ hoặc cả hai. Tập test nhỏ thực sự không nhỏ hơn bao nhiêu, nhưng nó đơn giản hơn vì bạn không thể có gương ở giữa phòng (chỉ có gương ở 4 cạnh biên). Điều này có nghĩa là chúng ta có thể lấy căn phòng ban đầu và phản chiếu nó liên tục qua mỗi trong bốn bức tường để bao phủ toàn bộ mặt phẳng. Điều này được hiển thị dưới đây:

Bây giờ hãy nhìn vào vị trí của bạn trong mỗi căn phòng phản chiếu này. Chúng tôi khẳng định rằng những vị trí này cung cấp chính xác các hướng bạn có thể nhìn để thấy hình ảnh phản chiếu của chính mình. Hãy thử lần theo một vài trường hợp và bạn sẽ thấy lý do tại sao.

Vì vậy, để giải bài toán, bạn có thể duyệt qua tất cả các vị trí này nằm trong khoảng cách \(D\) so với bạn và đếm xem chúng tạo ra bao nhiêu hướng duy nhất. (Hãy nhớ rằng tia sáng dừng lại khi nó quay trở lại bạn, vì vậy nếu hai hình ảnh phản chiếu nằm trên cùng một hướng chính xác, chỉ có hình ảnh gần nhất là có thể nhìn thấy).

Tập test 2 (Large)

Tập test lớn không khó hơn về mặt khái niệm, nhưng bạn sẽ phải cài đặt nhiều hơn. Ý tưởng là duyệt qua tất cả các ô vuông trong khoảng cách \(D\) so với vị trí bắt đầu của bạn và đi theo các tia sáng hướng về phía các ô vuông này. Cụ thể, có bao nhiêu tia sáng trong số này quay trở lại vị trí bắt đầu sau khoảng cách tối đa \(D\)? Thử thách đi theo các tia qua một lưới 2 chiều được gọi là "ray casting", và việc giải quyết nó một cách hiệu quả là chìa khóa của Wolfenstein 3D và các trò chơi khác thời đó.

Về lý thuyết thì không quá khó, nhưng việc cài đặt có thể trở nên rắc rối nếu bạn không thiết lập mọi thứ cẩn thận. Một cách tiếp cận hữu ích là trước tiên tập trung vào các tia di chuyển theo chiều dọc nhiều hơn chiều ngang. Sau đó, duyệt qua từng đường ngang mà tia đó chạm vào. Giữa mỗi bước này, nó sẽ chạm vào 0 hoặc 1 đường dọc, giúp việc xử lý khá đơn giản (ngoại trừ các góc!).

Về độ phức tạp, với mỗi hướng tiềm năng (có tối đa \(O(D^2)\) hướng như vậy), việc mô phỏng tia sáng mất \(O(D)\) hoặc \(O(H+W)\) tùy cách cài đặt. Tổng độ phức tạp sẽ nằm trong giới hạn cho phép.

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