Phân tích: Các cách nhìn khác nhau về chu vi

Bất chấp câu chuyện thú vị về tờ lịch và định nghĩa lạ lẫm về sự hạnh phúc, chúng tôi hy vọng bạn đã khám phá ra mô tả trừu tượng sau đây cho bài toán này:

Trên một bảng gồm \(N \times M\) ô vuông đơn vị, một số ô màu xanh, một số ô màu trắng và một số ô chưa được quyết định. Hãy tô mỗi ô chưa quyết định thành xanh hoặc trắng sao cho tổng chu vi của miền màu xanh là lớn nhất.

Chúng ta thấy rằng chu vi có thể được định nghĩa theo hai cách:

• (a) Tổng đóng góp từ mỗi ô màu xanh, như được chỉ ra trong đề bài.
• (b) Tổng đóng góp từ mỗi đoạn thẳng đơn vị. Tính 1 cho mỗi đoạn thẳng đơn vị ngăn cách hai ô có màu khác nhau. (Giả sử tất cả các ô bên ngoài bảng đều có màu trắng.)

Cách giải thích thứ hai rất hữu ích cho việc phân tích sau đây.

Có một số quan sát đơn giản có vẻ hữu ích. Ví dụ, đối với bất kỳ ô đơn vị chưa quyết định nào, nếu chúng ta đã quyết định rằng hai trong số các hàng xóm của nó là màu xanh, thì trong một giải pháp tối ưu, chúng ta có thể gán nó là màu trắng. Tuy nhiên, theo như chúng tôi biết, không có phương pháp tham lam (heuristics) nào như vậy cho ra một giải pháp đầy đủ và nhanh chóng cho bài toán này.

Một bài toán tương tự

Hãy thảo luận về một bài toán ít nhất là trông có vẻ giống với bài toán của chúng ta. Điều gì sẽ xảy ra nếu chúng ta muốn tối thiểu hóa chu vi thay vì tối đa hóa nó?

Chúng ta diễn đạt lại bài toán theo thuật ngữ lý thuyết đồ thị. Hãy để tập hợp \(NM\) ô vuông đơn vị là các đỉnh của chúng ta, và có một cạnh giữa hai ô vuông kề nhau. Nhiệm vụ của chúng ta là tô màu mỗi đỉnh chưa quyết định là màu xanh hoặc trắng, sao cho số lượng cạnh (trong đồ thị) giữa các đỉnh màu xanh và các đỉnh màu trắng là tối thiểu.

Điều này khá tuyệt vời, phải không? Nếu bạn thêm một nguồn \(s\) và một đích \(t\), thêm một cạnh từ \(s\) đến mọi đỉnh màu xanh với dung lượng vô hạn (4 là đủ) và một cạnh từ mọi đỉnh màu trắng đến \(t\) với dung lượng vô hạn, thì bài toán đang yêu cầu một lát cắt tối thiểu (minimum cut) từ \(s\) đến \(t\), có thể được giải bằng thuật toán luồng cực đại (max flow) yêu thích của bạn.

Giải bài toán gốc

Trong khi lát cắt tối thiểu có thể giải được trong thời gian đa thức bằng luồng cực đại, bài toán lát cắt tối đa (max-cut) lại quá khó trong các đồ thị tổng quát. Do đó, bài toán của chúng ta dường như vẫn khó hơn nhiều so với phiên bản tối thiểu hóa.

Tuy nhiên, chúng ta vẫn chưa sử dụng một sự thật quan trọng. Đồ thị của chúng ta không phải là đồ thị bất kỳ. Chúng ta chơi trò chơi này trên bảng \(N \times M\); đồ thị kết quả là đồ thị hai phía (hãy tưởng tượng nó như một bàn cờ vua). Việc tối đa hóa số cạnh giữa các đỉnh khác màu cũng giống như việc tối thiểu hóa số cạnh giữa các đỉnh cùng màu. Nói cách khác, nếu chúng ta đảo ngược màu của một nửa bàn cờ, bài toán sẽ quy về phiên bản tối thiểu hóa mà chúng ta đã thảo luận ở trên.

Chúng ta đánh dấu bảng theo kiểu bàn cờ vua, gán nhãn các ô đơn vị là lẻ hoặc chẵn. Sau đó, chúng ta đảo ngược màu của tất cả các ô chẵn (ví dụ: trắng thành xanh, xanh thành trắng, dấu hỏi vẫn là dấu hỏi nhưng ý nghĩa màu bị đảo ngược). Bây giờ hãy nhìn vào tính chất (b). Một đóng góp (cạnh giữa hai ô khác màu) sẽ trở thành không đóng góp (cạnh giữa hai ô cùng màu) và ngược lại. Vì tổng số cạnh là cố định, bài toán tối đa hóa quy về phiên bản tối thiểu hóa của nó (lát cắt tối thiểu).

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