Phân tích: House of Kittens

Có ba nhiệm vụ khác nhau bạn cần thực hiện để giải bài toán này:

• Làm thế nào để chuyển đổi đầu vào thành một định dạng thuận tiện hơn?
• Làm thế nào để tính toán \(C\) một cách hiệu quả?
• Làm thế nào để tìm một cách gán hương vị với đúng \(C\) hương vị một cách hiệu quả?

Tìm cách gán tối ưu

Hãy bắt đầu với \(C\). Quan sát quan trọng nhất cũng là một trong những quan sát đơn giản nhất. Gọi \(m\) là số lượng đỉnh tối thiểu trong một phòng đơn lẻ. Mèo con trong phòng đó có quyền tiếp cận tối đa \(m\) hương vị cỏ mèo, vì vậy chắc chắn \(C \le m\).

Thực tế, hóa ra \(C\) luôn bằng \(m\). Việc chứng minh điều này tương đương với nhiệm vụ thứ ba: chúng ta cần đưa ra một phương pháp gán hương vị luôn hoạt động với \(C = m\). Đây là phương pháp đó:

• Chọn một phòng bất kỳ. Gán các hương vị cho các đỉnh của nó sao cho tất cả \(C\) hương vị đều được sử dụng và không có hai đỉnh kề nhau nào sử dụng cùng một hương vị.
• Chọn một phòng kề với phòng bắt đầu. Phòng này sẽ có hai hương vị khác nhau đã được cố định cho hai đỉnh kề nhau. Điền vào các đỉnh còn lại như trước: tất cả \(C\) hương vị được sử dụng và không có hai đỉnh kề nhau nào sử dụng cùng một hương vị.
• Chọn một phòng khác kề với một trong các phòng đã xem xét trước đó. Một lần nữa, nó sẽ có hai hương vị khác nhau được cố định cho hai đỉnh kề nhau, và không có gì khác. Tiếp tục như trước.
• Tiếp tục theo cách tương tự cho đến khi tất cả các phòng đều hoàn thành.

Có hai điểm mấu chốt giúp phương pháp này hoạt động:

Điểm mấu chốt 1: Thực sự có thể gán các hương vị hợp lệ cho các đỉnh của một phòng đơn lẻ, ngay cả sau khi đã cố định các hương vị khác nhau cho hai đỉnh kề nhau. Bắt đầu với hai đỉnh kề nhau đó, gán \(C - 2\) hương vị còn lại cho \(C - 2\) đỉnh tiếp theo, sau đó chỉ cần tránh các đỉnh lân cận bằng nhau cho các đỉnh còn lại. Điều này luôn khả thi vì \(C \ge 3\) (trong các trường hợp đa giác có tường nội thất).

Điểm mấu chốt 2: Khi chúng ta đến một phòng mới, chỉ có tối đa hai đỉnh kề nhau là đã được cố định hương vị. Để thấy lý do, giả sử bạn vừa đến phòng \(R\) bằng cách đi qua bức tường \(W\). Khi đó, \(W\) chia ngôi nhà thành hai phần rời nhau, vì vậy đây sẽ là lần đầu tiên bạn chạm vào bất kỳ phòng nào ở cùng phía của \(W\) với \(R\). Đặc biệt, điều này có nghĩa là các đỉnh duy nhất đã được cố định là những đỉnh thuộc về \(W\).

Xử lý đầu vào

Thách thức kỹ thuật chính trong việc triển khai thuật toán này là tìm ra vị trí của tất cả các phòng và cách chúng kết nối với nhau.

Một cách tiếp cận là duy trì một danh sách các danh sách, đại diện cho các đỉnh trong mỗi phòng. Chúng ta bắt đầu chỉ với một phòng duy nhất: [[1, 2, ..., N]]. Đối với mỗi bức tường bên trong ngôi nhà, chúng ta quét qua các phòng cho đến khi tìm thấy phòng có cả hai đầu mút của bức tường, sau đó chia phòng đó thành hai. Sau đó, chúng ta phải cẩn thận một chút về thứ tự xử lý các phòng. Một lựa chọn là bắt đầu với một phòng bất kỳ, và sau đó chỉ xử lý các phòng tiếp theo khi chúng đã có hai đỉnh được xác định. Cách này chạy trong thời gian \(O(N^2)\).

Cũng có một số giải pháp thời gian gần như tuyến tính phức tạp hơn. Đối với mỗi đỉnh, ghi lại các cạnh đi ra từ đỉnh đó, được sắp xếp theo đầu mút đối diện. Bây giờ bạn có thể bắt đầu với một mặt (phòng), truy vết dọc theo tất cả các cạnh của nó, và sau đó đệ quy tiến tới các mặt bên kia của mỗi cạnh.

Bất kỳ phương pháp nào cũng hoạt động, vì vậy bạn có thể sử dụng phương pháp nào bạn thích.

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