Phân tích: Mascot Maze

Đây là một biến thể của bài toán tô màu đồ thị kinh điển, trong đó phòng, lối ra và linh vật lần lượt đóng vai trò đỉnh, cạnh và màu.

Những trường hợp có chu trình độ dài hai, tức hai phòng \(x,y\) sao cho có lối từ \(x\) tới \(y\) và lối từ \(y\) tới \(x\), hiển nhiên là bất khả thi. Phần sau sẽ chứng minh đây là những trường hợp bất khả thi duy nhất bằng một thuật toán luôn tô được mọi đồ thị không có chu trình độ dài hai.

Test Set 1

Với giới hạn nhỏ, có thể dùng quay lui: đệ quy thử mọi màu cho từng đỉnh. Một số kỹ thuật giúp tăng tốc, chẳng hạn duy trì tập màu không được dùng tại một đỉnh vì một hàng xóm đã được tô màu ấy trước đó.

Tuy nhiên, quay lui thuần túy khó vượt qua Test Set 2. Các lựa chọn màu sớm có thể khiến những đỉnh về sau không tô được, nhưng thuật toán phải mất rất lâu mới quay lại thay đổi các lựa chọn sớm ấy.

Test Set 2

Xét đồ thị \(G'\) có cạnh từ đỉnh này tới đỉnh kia nếu trong \(G\) có một đường đi độ dài \(1\) hoặc \(2\) nối chúng. Nói cách khác, \(G'\) chứa cạnh \((v,w)\) nếu \((v,w)\) là cạnh của \(G\), hoặc tồn tại hai cạnh \((v,x)\) và \((x,w)\) trong \(G\). Chỉ cần tô \(G'\) sao cho hai đỉnh kề nhau không cùng màu.

Mỗi đỉnh trong \(G'\) có bậc ra nhiều nhất \(6\): hai đỉnh cách một cạnh trong \(G\) và bốn đỉnh cách hai cạnh. Do đó, bậc vào trung bình cũng nhiều nhất \(6\), nên phải tồn tại ít nhất một đỉnh \(V\) có tổng bậc không quá \(6+6=12\). Bất kể hàng xóm của \(V\) đã nhận những màu nào, luôn còn ít nhất một màu khác cho \(V\), bởi nó có nhiều nhất \(12\) hàng xóm và ta có \(13\) màu.

Trường hợp duy nhất khiến \(G'\) không thể tô là khi nó chứa một khuyên, tức cạnh từ một đỉnh về chính nó. Khi đó, \(G\) cũng không thể thỏa yêu cầu.

Từ các quan sát trên, dùng thuật toán sau để tô \(G'\):

1. Tìm một đỉnh \(V\) có bậc không quá \(12\).
2. Tạm thời xóa \(V\) và mọi cạnh nối với nó.
3. Đệ quy tô phần đồ thị còn lại; phần này vẫn giữ mọi tính chất đã nêu.
4. Chèn lại \(V\) và tô màu cho nó.

Có thể cài đặt hiệu quả như sau:

• Xây dựng danh sách kề và mảng bậc cho \(G'\), theo dõi cả cạnh vào lẫn cạnh ra.
• Chạy tìm kiếm theo chiều rộng để lần lượt loại các đỉnh có bậc không quá \(12\). Ban đầu đưa mọi đỉnh như vậy vào hàng đợi và dùng danh sách kề để cập nhật hiệu quả. Nếu bậc một hàng xóm của đỉnh vừa bị loại giảm xuống \(12\), đưa hàng xóm đó vào hàng đợi. Không cần thật sự xóa đỉnh khỏi danh sách kề vì sẽ còn dùng về sau; chỉ cần cập nhật bậc. Trong quá trình BFS, lưu lại thứ tự duyệt các đỉnh.
• Duyệt các đỉnh theo thứ tự ngược lại và tô tham lam: thử từng màu, chọn màu chưa xuất hiện ở bất kỳ hàng xóm nào đã tô.

Mọi bước đều thực hiện được trong thời gian tuyến tính, nên tổng độ phức tạp là tuyến tính.

Một số hướng kinh nghiệm như tìm kiếm cục bộ cũng có thể hoạt động nếu được cài đặt hiệu quả.

Dữ liệu kiểm thử

Google khuyến nghị bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Phân tích chính thức của Google Code Jam 2022, Vòng 3, bài Mascot Maze.