Phân tích: Lights

Có nhiều cách khác nhau để giải bài toán này. Các giải pháp có thể được chia thành hai loại tiếp cận. Một cách là giải bài toán một cách chính xác (hoặc với độ chính xác tùy ý), cách còn lại là xấp xỉ câu trả lời với độ chính xác đủ cao. Các giải pháp chính xác thường cố gắng chia hình vuông thành các vùng nhỏ có cùng màu, tính diện tích của từng vùng riêng biệt và cộng tổng lại cho mỗi màu. Chúng ta sẽ thảo luận về những cách này trước.

Giao điểm của các hình (chủ yếu là) tam giác

Đầu tiên, hãy xem xét chỉ một nguồn sáng. Chúng ta muốn tính tổng diện tích được chiếu sáng bởi nguồn sáng đó. Để làm điều đó, hãy tính các đường tiếp tuyến từ nguồn sáng đến mỗi cột, và các đường từ nguồn sáng đến mỗi góc của căn phòng, sau đó xem xét từng "hình nón" giữa hai đường thẳng kề nhau một cách riêng biệt. Mỗi hình nón sẽ kết thúc bằng việc chạm vào tường hoặc chạm vào một cột. Trong trường hợp đầu tiên, chúng ta có một hình tam giác, diện tích của nó có thể dễ dàng tính được. Trong trường hợp thứ hai, chúng ta có một "hình tam giác giả", tức là một hình tam giác trừ đi một hình viên phân (segment of a disk). Ở đây, chúng ta cần trừ đi diện tích của hình viên phân đó. Chúng ta có thể tính diện tích của hình viên phân bằng cách lấy diện tích của hình quạt (sector) trừ đi diện tích của một hình tam giác.

Khi đã có tổng diện tích được bao phủ bởi mỗi nguồn sáng, chúng ta cần thêm một thứ nữa: diện tích được bao phủ bởi cả hai nguồn sáng. Chúng ta có thể lấy từng cặp tam giác hoặc tam giác giả được tạo ra ở bước trước và tính diện tích chung giữa chúng. Bây giờ chúng ta cần tính diện tích giao nhau của hai tam giác hoặc tam giác giả.

Một cách đơn giản để tiếp cận việc này là trước tiên coi các tam giác giả như các tam giác (bao gồm cả phần hình viên phân). Bây giờ chúng ta tính toán phần giao giữa hai tam giác, kết quả là một đa giác (tối đa sáu cạnh). Nếu một hoặc cả hai tam giác là tam giác thực sự, hoặc khi các cột bị trừ đi từ hai tam giác giả là khác nhau, thì đa giác đó chính là câu trả lời đúng - không cần phải tính đến các hình viên phân bị trừ đi, vì mỗi hình viên phân đó nằm ngoài tam giác kia.

Trường hợp khó khăn duy nhất xảy ra khi chúng ta có hai tam giác giả cùng kết thúc tại một cột. Trong trường hợp đó, trước tiên chúng ta tính đa giác giao nhau, sau đó trừ đi phần cột khỏi đa giác. Để làm điều đó, hãy loại bỏ các cạnh và phần của các cạnh đa giác nằm bên trong hình tròn và thay thế chúng bằng một cạnh. Câu trả lời sẽ là diện tích của đa giác đã thu gọn, một lần nữa trừ đi một hình viên phân bị cắt bởi một đường thẳng, điều mà chúng ta đã biết cách tính.

Quét đường (Line sweeping)

Quét đường là một kỹ thuật phổ biến trong hình học tính toán. Chúng ta quét một đường thẳng đứng từ cạnh trái sang cạnh phải. Như trong giải pháp trên, các tia đáng quan tâm là các tia tiếp tuyến từ các nguồn sáng đến các hình tròn. Các thời điểm thú vị là khi tọa độ \(x\) của đường thẳng đứng đạt đến một trong các giá trị sau: (1) Một nguồn sáng. (2) Một cột bắt đầu hoặc kết thúc. (3) Một tia đáng quan tâm chạm hoặc cắt một hình tròn, hoặc chạm vào tường. (4) Hai tia đáng quan tâm cắt nhau.

Bây giờ, gọi \(x_1 < x_2\) là hai thời điểm thú vị kề nhau. Dải thẳng đứng giữa \(x_1\) và \(x_2\) được chia thành các phần. Mỗi phần được giới hạn trên và dưới bởi một đoạn tổng quát -- một đoạn thẳng hoặc một cung tròn. Theo định nghĩa về các thời điểm thú vị, sẽ không có gì đặc biệt xảy ra ở giữa, và mỗi phần sẽ có một màu duy nhất. Vì vậy, chúng ta có thể lấy mẫu một điểm bất kỳ từ mỗi phần để quyết định màu sắc. Các phần này không lồi, nhưng đây không phải là vấn đề -- chúng lồi trên bất kỳ đường thẳng đứng nào nên chúng ta có thể dễ dàng tìm thấy một điểm nằm bên trong mỗi phần. Diện tích của mỗi phần cũng dễ tính -- về cơ bản nó là một hình thang, có thể biến đổi thành hình tam giác nếu biên trên và biên dưới gặp nhau tại một đầu, và ta cần trừ đi một hình viên phân cho mỗi biên dạng cung tròn.

Quét đường thường được sử dụng với các cấu trúc dữ liệu tốt để đạt được độ phức tạp mong muốn. Nhưng đó không phải là mối quan tâm chính của chúng ta ở đây. Chúng ta sử dụng nó vì sự đơn giản trong cài đặt -- các thao tác hình học duy nhất cần thiết ở đây là giao điểm giữa đường thẳng và hình tròn.

Xấp xỉ

Bài toán yêu cầu sai số tương đối hoặc tuyệt đối tối đa là \(10^{-5}\), trong khi tổng diện tích phòng là \(10000\). Các trường hợp cần cẩn thận nhất là khi một trong bốn màu có diện tích nhỏ hơn 1, trong trường hợp đó sai số chúng ta có thể mắc phải so với diện tích của cả căn phòng là \(10^{-9}\).

Cách tiếp cận đơn giản nhất là lấy mẫu rất nhiều điểm ngẫu nhiên hoặc theo một lưới đều, tính màu của mỗi mẫu và giả định rằng mẫu đó đại diện cho câu trả lời chính xác. Tuy nhiên, ước tính sai số ở trên gợi ý rằng để đạt được đủ độ chính xác, chúng ta cần lấy mẫu cỡ \(10^9\) điểm (hoặc nhiều hơn, do sai lệch ngẫu nhiên). Điều này là quá nhiều để một giải pháp chạy trong giới hạn thời gian. Cần một cách tiếp cận thông minh hơn.

Việc tính diện tích có thể được xem như bài toán tính tích phân hai lớp. Một cách tiếp cận kết hợp cũng khả thi: chúng ta có thể xem nó như một tích phân một lớp theo tọa độ \(x\), và với mỗi tọa độ \(x\) chúng ta lấy mẫu, chúng ta có thể tính toán câu trả lời chính xác bằng cách xem đoạn nào của đường thẳng đứng có màu gì. Bài toán con một chiều này đơn giản hơn một chút so với việc giải trực tiếp bài toán hai chiều một cách chính xác.

Trong cả hai trường hợp, cho dù chúng ta tính tích phân hai lớp hay chỉ là tích phân một lớp cho một hàm phức tạp hơn, chúng ta cần một cách thông minh để xấp xỉ tích phân. Lấy mẫu đồng nhất hoặc ngẫu nhiên là không đủ.

Bạn có thể tìm kiếm trên web các phương pháp tích phân số. Trong bài toán này, cần một thuật toán thích nghi (adaptive algorithm), có nghĩa là chúng ta lấy mẫu nhiều hơn ở các vùng "thú vị" và ít mẫu hơn ở các vùng ít "thú vị". "Thú vị" có thể được định nghĩa là "có sự thay đổi lớn về giá trị" (đạo hàm bậc nhất lớn) hoặc "có sự thay đổi mạnh về giá trị" (đạo hàm bậc hai lớn).

Một thuật toán đơn giản là viết thủ tục tích phân dưới dạng một hàm đệ quy. Chúng ta đệ quy thử chia khoảng thành các khoảng nhỏ hơn và xem câu trả lời thay đổi bao nhiêu thông qua việc tăng độ chính xác như vậy. Chúng ta dừng đệ quy khi câu trả lời thay đổi rất ít, điều đó có nghĩa là khoảng đó đủ nhỏ hoặc hàm đủ mượt trong khoảng đó. Điều này sẽ dẫn đến việc lấy mẫu các vùng "thú vị" chính xác hơn.

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