Test Set nhỏ

Trong Test Set nhỏ, sân có nhiều nhất 16 ô cần chọn hướng hàng rào, nên có tối đa \(2^{16}=65536\) mê cung. Vì mỗi ô đều có một đường chéo, mỗi mê cung tạo ra một song ánh giữa các cận thần ở vành ngoài; lối của hai cặp khác nhau không thể giao nhau, nên ta không cần kiểm tra riêng điều đó. Chỉ cần sinh mọi mê cung và xác định hiệu quả các ô ngoài được ghép với nhau.

Có thể coi hàng rào là gương và chiếu một tia sáng từ một ô ngoài, vuông góc với cạnh sân. Ở mỗi ô, tia phản xạ 90 độ trên gương rồi đi sang ô tiếp theo, cho đến khi ra khỏi mê cung tại ô ngoài được ghép với điểm xuất phát.

Một cách tương đương là tưởng tượng vẽ cả hai đường chéo trong mỗi ô, chia ô thành bốn tam giác. Lập đồ thị có các tam giác này làm đỉnh, nối hai tam giác kề nhau nếu không bị hàng rào chặn. Bắt đầu từ tam giác ứng với cạnh vào của một cận thần và duyệt tới cạnh ngoài khác, hoặc tìm các thành phần liên thông, ta biết các cặp được nối.

Test Set lớn

Với tối đa 100 ô, vét cạn không còn khả thi. Ta sẽ dựng hàng rào để lần lượt nối các cặp. Dễ nhất là hai ô ngoài kề nhau qua một cạnh hoặc quanh một góc. Hai ô sát góc trên trái có thể nối trực tiếp bằng một hàng rào /. Mặc dù hình minh họa bộ test 3 nối hai ô sát góc trên phải bằng một đường vòng dài, ta cũng có thể nối thẳng và để phần giữa khu vườn không thể tới được. Đường thẳng chỉ chiếm hai tam giác ở góc; mọi đường khác giữa hai ô này cũng phải chiếm hai tam giác ấy, nên không có lý do chọn đường phức tạp hơn.

Hai ô ngoài kề nhau dọc một cạnh có thể nối bằng hai hàng rào, chiếm bốn tam giác. Mọi đường nối đều phải dùng hai tam giác sát biên. Có thể dựng một đường không đi qua hai tam giác còn lại, nhưng khi đó chúng chắc chắn bị cô lập và không thể được tiếp cận từ cạnh khác. Vì vậy, một đường nối hoặc chiếm cả bốn tam giác của đường đơn giản nhất, hoặc khiến một phần trong đó vô dụng; đường phức tạp hơn không đem lại lợi ích.

Nếu mỗi cặp đều có một đường tối ưu duy nhất dễ xác định, ta chỉ cần dựng các đường ấy và báo vô nghiệm khi chúng giao nhau. Tuy nhiên, với một cặp nối cạnh trái và cạnh phải, tùy các đường khác, ta có thể đi qua nửa trên hoặc nửa dưới khu vườn. Không có một đường tối ưu duy nhất rõ ràng. Dẫu vậy, ta có thể xét đường cao nhất hoặc thấp nhất, lần lượt chừa nhiều chỗ nhất cho các đường bên dưới hoặc bên trên. Chẳng hạn, đường cao nhất phải dùng ít không gian nhất để nối cặp đang xét cùng mọi cặp phía trên nó; tồn tại một cách tối ưu để làm vậy.

Trong phần còn lại, giả sử bài toán có lời giải. Khi có lời giải, chiến lược dưới đây sẽ tìm ra nó. Khi không có, chiến lược có thể dựng sai, nhưng ta dễ phát hiện bằng cách kiểm tra mê cung như ở lời giải Test Set nhỏ.

Gọi một nhóm cặp là một số dương các cặp mà toàn bộ ô ngoài của chúng tạo thành một đoạn liên tục thật sự trên chu vi, nhưng không phải toàn bộ chu vi. Với một cặp nối cạnh trái và phải, ta có thể xét nhóm cặp nằm phía trên đường nối, rồi nhóm gồm cả các cặp phía trên và chính cặp này. Mỗi nhóm có một tập tam giác tối ưu để nối mọi cặp trong đoạn. “Tối ưu” có hai tính chất: ta có thể dựng các đường nối nhóm mà không chiếm tam giác ngoài tập (tính đủ), và nếu mọi cặp trong nhóm đã được nối thì đường của cặp ngoài nhóm không bao giờ có thể chiếm tam giác trong tập (tính cần).

Ta đã biết tập tối ưu cho nhóm chỉ gồm một cặp ô ngoài kề nhau. Nếu hai nhóm ghép lại thành một nhóm lớn hơn, tập tối ưu mới là hợp của hai tập nhỏ; dưới giả thiết tồn tại lời giải, hợp này thỏa cả tính đủ lẫn tính cần.

Xét lại cặp nối cạnh trái và phải. Nếu đã có tập tối ưu cho nhóm phía trên, ta mở rộng nó thành tập tối ưu cho nhóm gồm thêm cặp này bằng cách cho đường mới đi cao nhất có thể, bám sát các đường phía trên. Có thể chứng minh tập sau khi thêm vẫn tối ưu. Tổng quát hơn, với bất kỳ cặp không kề nào, nếu đã có tập tối ưu của nhóm ở một phía, ta thêm một đường bám sát tập đó nhất có thể. Nhờ vậy, ta quy nạp xây các tập tối ưu cho đến khi bao phủ mọi cặp. Toàn bộ các cặp không được gọi là một nhóm hợp lệ vì định nghĩa tối ưu ở trên không áp dụng cho trường hợp ấy.

Thuật toán

1. Ban đầu chưa đặt hàng rào nào.
2. Xử lý các cặp theo thứ tự tăng dần của khoảng cách dọc chu vi giữa hai ô; hòa có thể phá tùy ý.
3. Gọi hai đầu là \(A,B\) sao cho cung \(A\to B\) theo chiều kim đồng hồ ngắn hơn cung ngược chiều. Nhờ thứ tự xử lý, các đường cho mọi điểm nằm bên trái đường \(A\to B\) sắp dựng đã có sẵn.
4. Đi qua mê cung từ \(A\) theo phép tương tự tia sáng. Ta muốn bám trái tối đa: khi gặp ô chưa có hàng rào, chọn đường chéo khiến tia rẽ trái. Khi ra khỏi sân, kiểm tra điểm ra có đúng là \(B\) hay không; nếu bài vô nghiệm, tia có thể ra ở chỗ khác.
5. Điền tùy ý mọi ô còn lại.

Mã Python mẫu dưới đây mã hóa hướng bằng số nguyên để phép quay và di chuyển có thể thực hiện gọn bằng toán tử bit và tra mảng:

def position(v, R, C):
    # Map from outer cell number to a direction facing into the maze
    # and the position of the outer cell
    # 0->downwards, 1->leftwards, 2->upwards, 3->rightwards
    if v <= C: return 0, v-1, -1
    v -= C
    if v <= R: return 1, C, v-1
    v -= R
    if v <= C: return 2, C-v, R
    v -= C
    return 3, -1, R-v

def move(x, y, direction):
    return x + [0,-1,0,1][direction], y + [1,0,-1,0][direction]

def solve(R, C, permutation):
    board = [[None] * C for _ in range(R)]
    size = 2*(R+C)
    permutation = zip(permutation[::2], permutation[1::2])
    permutation.sort(key=lambda(a,b): min((b-a)%size, (a-b)%size))
    for start, end in permutation:
        if (start-end) % size > R+C:
            start, end = end, start
        direction, x, y = position(start, R, C)
        x, y = move(x, y, direction)
        while 0<=x<C and 0<=y<R:
            if board[y][x] is None:
                board[y][x] = "/\\"[direction & 1]
            direction ^= {"/": 1, "\\": 3}[board[y][x]]
            x, y = move(x, y, direction)
        if (x, y) != position(end, R, C)[1:]:
            return "IMPOSSIBLE"
    return "\n".join("".join(c or "/" for c in row) for row in board)

if __name__ == "__main__":
    for t in range(1, input() + 1):
        R, C = map(int, raw_input().split())
        permutation = map(int, raw_input().split())
        print "Case #%d:" % t
        print solve(R, C, permutation)

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2016, Vòng 2.