Phân tích: Bacteria

Việc dữ liệu đầu vào là một tập hợp các hình chữ nhật không phải là yếu tố cốt lõi của bài toán này. Điều đó chỉ nhằm giới hạn lượng dữ liệu cần tải xuống. Vì vậy, hãy tạm quên các hình chữ nhật và thay vào đó xem xét bất kỳ cấu hình ban đầu nào của \(n\) vi khuẩn trên lưới. Thử thách ở đây là tính toán kết quả thật nhanh. Việc mô phỏng từng bước sẽ không đủ tốt. Chúng ta sẽ hướng tới một giải pháp có độ phức tạp \(O(n)\).

Các ví dụ

Một cách để bắt đầu tiếp cận bài toán này là xem xét các ví dụ:

• Một hình chữ nhật kích thước \(H \times W\) vi khuẩn.
• Một hình chữ nhật \(H \times W\) nhưng vi khuẩn chỉ nằm trên bốn cạnh biên.
• Vi khuẩn dọc theo đường chéo "loại 1" (đường chéo Tây Nam - Đông Bắc).
• Vi khuẩn dọc theo đường chéo "loại 2" (đường chéo Tây Bắc - Đông Nam).
• Một đường đi ngẫu nhiên nơi mỗi cặp vi khuẩn được kết nối theo chiều ngang, chiều dọc hoặc dọc theo đường chéo loại 1.

Nếu bạn thử các ví dụ này, bạn sẽ tìm thấy cảm hứng cho bài toán tổng quát. Chúng ta gọi một đường chéo loại 1 cao hơn đường chéo khác nếu nó nằm về phía bắc (và do đó về phía tây) của đường chéo kia. Nếu cấu hình ban đầu là một "mảnh kết nối" (chúng ta sẽ định nghĩa chính xác sau), ta có thể tìm đường chéo loại 1 cao nhất chứa ít nhất một vi khuẩn \(X + Y = C\), điểm cực phải chứa vi khuẩn \(X = X_{max}\), và điểm cực dưới chứa vi khuẩn \(Y = Y_{max}\). Ta khẳng định rằng sau một lượt, cấu hình vẫn sẽ là một mảnh kết nối duy nhất, đường chéo cao nhất sẽ trở thành \(X + Y = C+1\), và các tọa độ \(X_{max}, Y_{max}\) sẽ không đổi. Điều này tiếp diễn cho đến giây cuối cùng khi tất cả thu gọn về một điểm duy nhất \((X_{max}, Y_{max})\). Vậy số giây trước khi mọi thứ biến mất là \(X_{max} + Y_{max} - C + 1\).

Một điều lưu ý là ví dụ thứ 3 và thứ 4 hoạt động rất khác nhau. Trong ví dụ 3, số lượng vi khuẩn giảm đi 1 sau mỗi lượt, trong khi ở ví dụ 4, tất cả vi khuẩn biến mất ngay lập tức.

Giải pháp

Định nghĩa một đồ thị trên các vi khuẩn. Hai vi khuẩn là láng giềng nếu chúng kề nhau trên lưới theo đường ngang, đường dọc, hoặc đường chéo loại 1. Đầu tiên, chúng ta tìm các thành phần liên thông của đồ thị này.

Đây là chìa khóa để giải quyết toàn bộ bài toán. Nó khá giống với đồ thị lưới thông thường nơi mỗi nút có 8 láng giềng, ngoại trừ việc chúng ta không xét 2 hướng dọc theo đường chéo loại 2. Nhìn lại ví dụ 3 và 4: nếu bắt đầu với \(n\) nút, ví dụ 3 chỉ có một thành phần liên thông, trong khi ví dụ 4 có \(n\) thành phần liên thông.

Chúng ta quan sát thấy sau mỗi lượt, một thành phần liên thông sẽ sinh ra một thành phần liên thông mới (trừ khi nó chỉ là một điểm và biến mất), và các thành phần khác nhau sẽ không bị kết nối lại với nhau.

Vì vậy, kết quả là thời gian biến mất tối đa trong tất cả các thành phần liên thông. Đối với một mảnh (thành phần liên thông), ta tìm đường chéo loại 1 cao nhất \(X + Y = C\), cũng như các tọa độ cực đại \(X_{max}\) và \(Y_{max}\). Số lượt để mảnh đó biến mất là \(X_{max} + Y_{max} - C + 1\).

Chứng minh

Giải pháp của chúng ta phụ thuộc rất nhiều vào một số quan sát then chốt. Nếu tự thử vài ví dụ, bạn có thể kiểm chứng bằng thực nghiệm rằng các quan sát này hẳn phải đúng. Tuy nhiên, để phần trình bày được đầy đủ, dưới đây là một phác thảo chứng minh chặt chẽ hơn.

Trong phần thảo luận sau, ta cố định một cấu hình gọi là trạng thái cũ và xét trạng thái mới thu được sau một lượt. Khi nói đến một mảnh liên thông, ta luôn giả sử trường hợp không tầm thường, tức mảnh đó có ít nhất 2 điểm.

Với mỗi vi khuẩn trong trạng thái mới, hãy xét lý do nó tồn tại. Nếu nó đã có trong trạng thái cũ, ta quy nguyên nhân tồn tại của nó cho tập gồm chính nó và láng giềng phía bắc và/hoặc phía tây của nó. Nếu nó không có trong trạng thái cũ, ta chỉ quy nguyên nhân tồn tại của nó cho tập gồm hai láng giềng phía bắc và phía tây. Trong cả hai trường hợp, ta gọi tập như vậy là tập quy nguyên (credit set) của vi khuẩn đó.

Mệnh đề 1. Nếu trạng thái cũ là một mảnh duy nhất và đường chéo loại 1 cao nhất là \(X + Y = C\), thì ở trạng thái mới, đường chéo loại 1 cao nhất sẽ trở thành \(X + Y = C+1\).

Chứng minh. Xét một vi khuẩn tại vị trí \((X, Y)\) trên đường chéo cao nhất của trạng thái cũ. Vì đây là đường chéo cao nhất, vi khuẩn đó không có láng giềng phía bắc hoặc phía tây, nên nó sẽ chết. Do đó, đường chéo \(X + Y = C\) sẽ hoàn toàn trống ở trạng thái mới.
Bây giờ chọn vi khuẩn nằm cực nam nhất ở trạng thái cũ trên đường chéo \(X + Y = C\). Gọi vị trí của nó là \((X, C-X)\). Nếu cũng có một vi khuẩn tại \((X+1, C-X-1)\) ở trạng thái cũ, sẽ có một vi khuẩn tại \((X+1, C-X)\) ở trạng thái mới. Ngược lại, vì \((X, C-X)\) thuộc một mảnh liên thông và nằm trên đường chéo cao nhất, phải có một vi khuẩn tại \((X, C-X+1)\) hoặc \((X+1, C-X)\) ở trạng thái cũ, và theo quy tắc, vi khuẩn này sẽ sống sót sang trạng thái mới. Do đó, luôn có ít nhất một vi khuẩn trên đường chéo \(X + Y = C+1\) ở trạng thái mới.

Mệnh đề 2. Nếu trạng thái cũ là một mảnh duy nhất, tọa độ \(X\) cực đại và tọa độ \(Y\) cực đại sẽ không đổi ở trạng thái mới.

Mệnh đề 3. Nếu trạng thái cũ là một mảnh liên thông duy nhất, trạng thái mới cũng sẽ là một mảnh liên thông duy nhất.

Để thấy Mệnh đề 3, lưu ý rằng nếu trạng thái cũ liên thông, thì bất kỳ hai "tập tín dụng" (credit sets) nào cũng có thể được nối với nhau bằng một đường đi gồm các đoạn ngang, dọc và chéo loại 1. Như hình dưới đây, bất kỳ đoạn nào từ đường đi đó cũng sẽ sinh ra các đoạn liên thông ở trạng thái mới:

Cuối cùng, chúng ta chứng minh rằng các mảnh khác nhau sẽ không bị gộp lại trong một lượt.

Mệnh đề 4. Nếu hai vi khuẩn là láng giềng ở trạng thái mới, thì các tập tín dụng của chúng đều thuộc về cùng một mảnh ở trạng thái cũ.

Điều này hiển nhiên đúng nếu cả hai vi khuẩn đều đã tồn tại ở trạng thái cũ. Nếu không, nó rơi vào một trong các trường hợp trong hình dưới đây. Hai vi khuẩn là các điểm khoanh tròn. Điểm xanh lam cho biết vi khuẩn đã có ở trạng thái cũ, điểm đỏ cho biết vi khuẩn chỉ có ở trạng thái mới. Các ngôi sao vàng đại diện cho các điểm trong tập tín dụng. Trong mọi tình huống, hoặc ta đạt tới một cấu hình không thể xảy ra, hoặc dẫn tới việc các tập tín dụng rõ ràng là liên thông.

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