Test Set 1: quy hoạch động

Có nhiều cách giải Test Set 1. Cách trực tiếp nhất là quy hoạch động. Vì không có gương, mỗi tia phủ một dãy ô không phải tường liên tiếp theo chiều ngang hoặc dọc. Ta xử lý các cột từ trái sang phải và, với mỗi hàng, lưu một trong bốn trạng thái:

1. Có một tia đi vào, phát ra từ hàng này ở một cột đã xử lý và chưa bị tường chặn.
2. Cần một tia: có ít nhất một ô ở phần đã xử lý của hàng chưa được phủ nhưng vẫn có thể nhận tia vì chưa có tường chắn.
3. Không có và cũng không thể nhận tia, vì nếu có thì sẽ phá một máy phát dọc đã gặp trước đó trên hàng.
4. Không thuộc các trường hợp trên: dãy ô trước đó đã được tia dọc phủ hết, nên có thể bắn ngang trên hàng nhưng chưa bắt buộc.

Ở mỗi cột, thử mọi tổ hợp hướng cho các máy phát trong cột và kiểm tra có chuyển hợp lệ sang trạng thái cột kế tiếp không. Với từng hàng, phải kết hợp trạng thái đi vào với ô hiện tại; ô đó có thể là ô trống đã phủ hoặc chưa phủ, máy phát dọc hoặc ngang, hay tường. Có \(4^R C\) trạng thái, mỗi trạng thái thử tối đa \(2^R\) tổ hợp hướng và mỗi lần kiểm tra quét \(R\) ô, nên cận thời gian là \(O(8^RCR)\). Có thể tinh chỉnh cận vì nhiều tổ hợp trạng thái không bao giờ xảy ra, nhưng không cần thiết.

Test Set 1: cách tham lam

Một cách khác chỉ dựa vào việc không có gương:

1. Nếu một hướng của máy phát có thể phá máy khác, bắt buộc quay nó theo hướng còn lại. Nếu cả hai hướng đều phá máy, bài toán vô nghiệm.
2. Nếu một ô chưa phủ chỉ có thể được phủ bởi đúng một máy chưa cố định, bắt buộc hướng máy đó về phía ô. Nếu một ô còn lại không thể được phủ vì mọi máy từng có thể chiếu nó đã bị ép sang hướng khác, bài toán vô nghiệm.
3. Cho tất cả máy chưa cố định bắn ngang; cho tất cả bắn dọc cũng được.

Sau hai bước đầu, nếu một ô vẫn chưa phủ thì nó có đúng hai máy chưa cố định có thể chiếu tới: một theo ngang và một theo dọc. Nếu có ít nhất hai máy cùng chiếu theo một hướng, bước 1 đã cố định tất cả chúng; nếu tổng cộng chỉ có một máy, bước 2 đã cố định nó. Chọn cùng một hướng cho mọi máy còn lại bảo đảm với mỗi ô như vậy có đúng một máy quay đúng hướng để phủ ô.

Test Set 2: đường tia qua gương

Cách tham lam trên gợi ý một khái quát cho Test Set 2. Khi không có gương, mỗi ô nằm tại giao của một đoạn ngang và một đoạn dọc gồm các ô liên tiếp không có tường. Mỗi đoạn nằm giữa hai tường, hai biên đối diện, hoặc một tường và một biên. Đoạn có 0 máy phát thì buộc từng ô phải được phủ từ hướng kia; có 1 máy thì để lại lựa chọn; có nhiều máy thì buộc mọi máy trên đoạn quay vuông góc với đoạn.

Khi có gương, thay “đoạn” bằng đường tia. Một đường tia là tập các cặp \((c,d)\), với \(c\) là ô trống hoặc ô máy phát và \(d\) là ngang hoặc dọc. Hai cặp \((c,d)\) và \((c',d')\) cùng đường khi và chỉ khi một máy đặt tại \(c\), bắn theo \(d\) và tạm bỏ qua mọi máy khác, sẽ tạo tia đi qua \(c'\) theo \(d'\).

Trong hình, đường đỏ và xanh dương đi qua cùng tập ô trống nhưng gồm những cặp (ô, hướng) khác nhau. Đường cam đi qua cùng một ô hai lần: nó chứa cả \((c,\text{ngang})\) và \((c,\text{dọc})\) với \(c\) là ô trống ngoài cùng bên phải ở hàng cuối. Một số đường chỉ có một cặp, như các đường xanh ngọc, tím và nâu. Có đường tự khép kín như đường hồng, trong khi đường khác kết thúc ở tường hoặc biên; ta gọi loại đầu là đường vòng.

Gọi \(o(d)\) là hướng vuông góc: \(o(\text{ngang})=\text{dọc}\) và ngược lại. Các đường không chứa đúng một máy phát tạo những hệ quả tức thời:

1. Nếu một đường chứa cả \((c,d)\) và \((c,o(d))\) với \(c\) là máy phát, bài toán vô nghiệm: máy đó tự phá mình ở cả hai hướng.
2. Nếu đường vòng chứa \((c,d)\) với \(c\) là máy phát, máy bắt buộc quay theo \(o(d)\).
3. Nếu một đường chứa ít nhất hai cặp \((c_i,d_i)\) mà \(c_i\) là máy phát, mỗi máy \(c_i\) bắt buộc quay theo \(o(d_i)\).
4. Nếu đường không có máy nhưng chứa cả \((c,d)\) và \((c,o(d))\) với \(c\) là ô trống, bài toán vô nghiệm vì không thể phủ \(c\).
5. Nếu đường không có máy, xét mỗi \((c_i,d_i)\) trên đó và đường \(p\) chứa \((c_i,o(d_i))\). Nếu \(p\) chứa đúng một cặp \((c,d)\) mà \(c\) là máy phát, bắt buộc máy đó quay theo \(d\); nếu \(p\) không chứa đúng một máy, bài toán vô nghiệm.

Nếu một máy bị ép theo hai hướng khác nhau bởi cùng một bước hay các bước khác nhau, bài toán vô nghiệm. Đây chính là khái quát của hai bước đầu trong cách tham lam Test Set 1.

Mô hình 2-SAT

Sau các ép buộc trên, một số ô có thể chưa được phủ. Mỗi ô như vậy nằm tại giao của hai đường khác nhau, và mỗi đường chứa đúng một máy chưa cố định. Cụ thể, với ô \(c\), hai đường chứa \((c,\text{ngang})\) và \((c,\text{dọc})\) đi qua các máy tương ứng ở cặp \((s_1,d_1)\) và \((s_2,d_2)\). Phủ \(c\) đòi hỏi \(s_1\) quay theo \(d_1\) hoặc \(s_2\) quay theo \(d_2\), hoặc cả hai. Nếu \(s_1=s_2\) thì \(d_1\ne d_2\), nên mọi cách định hướng máy đó đều thỏa yêu cầu.

Gán một biến logic cho mỗi máy, với true và false ứng với hai hướng. Mỗi yêu cầu của ô là phép tuyển của hai literal. Ta cần làm đúng đồng thời hội của mọi phép tuyển như vậy — chính là bài toán 2-SAT. Với mệnh đề \((a\lor b)\), thêm hai cạnh kéo theo \(\neg a\to b\) và \(\neg b\to a\). Tìm các thành phần liên thông mạnh; nếu một biến và phủ định của nó cùng thành phần thì IMPOSSIBLE, nếu không thứ tự tô-pô cho một phép gán, rồi đổi nó thành -/|.

Không nhất thiết phải thực hiện riêng pha ép buộc. Mỗi ô trống trực tiếp sinh một yêu cầu trên tối đa hai máy, một theo mỗi hướng. Nếu chỉ có một literal \(L\), mã hóa thành \((L\lor L)\). Một máy có hướng bắn trúng máy khác cũng sinh mệnh đề đơn buộc nó quay hướng kia. Như vậy mọi yêu cầu đều đi thẳng vào cùng thể hiện 2-SAT và lời giải ngắn gọn hơn.

Mô hình logic cũng chứng minh rất gọn bước 3 của cách tham lam Test Set 1: không có gương, mỗi mệnh đề chưa xử lý có đúng một literal ngang và một literal dọc, tức một literal dương và một literal âm nếu quy ước biến nhất quán. Gán mọi biến true làm mỗi mệnh đề đúng nhờ literal không phủ định; gán tất cả false cũng đúng nhờ literal phủ định.

Phân tích trên trình bày theo quá trình suy luận từng bước, không cần một bước nhảy ý tưởng lớn. Một số người có thể nhận ra 2-SAT ngay từ việc mỗi ô cho yêu cầu trên tối đa hai máy. Bài cũng dễ gợi ra nhiều heuristic tham lam kết hợp vét cạn hoặc quay lui. Bản thân 2-SAT có thể giải đa thức bằng một số cách quay lui hoặc thuật toán đồ thị với nhiều quyết định tham lam bên dưới; vì vậy nhiều thuật toán không gọi tên 2-SAT vẫn đúng do về bản chất đang làm cùng việc.

Theo dõi trạng thái (ô, hướng) dựng các đường tia và mệnh đề trong thời gian tuyến tính theo số trạng thái; SCC cũng tuyến tính theo kích thước đồ thị kéo theo.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, Round 2, bài Beaming With Joy; kho Google Coding Competitions (Apache-2.0).