Phân tích: Rains Over Atlantis

Một lời giải hiển nhiên (dùng được cho dữ liệu nhỏ) là mô phỏng. Rắc rối xuất hiện khi độ cao lớn và \(M\) nhỏ, nên ta cần thực hiện nhiều bước cùng lúc.

Với bản đồ độ cao hiện tại, có thể xác định mực nước — khu vực nào ngập và khu vực nào không — bằng một lần chạy Dijkstra trong thời gian \(RC\log(RC)\).

Thủ tục bước đơn:

1. Tính mực nước cho mọi ô.
2. Với mỗi ô, xác định nó có ngập không; nếu không, tìm mực nước thấp nhất trong các ô kề.
3. Tạo bản đồ mới bằng cách giảm mọi độ cao theo lượng xói mòn thích hợp, rồi tăng bộ đếm ngày một đơn vị.

Đây cũng là một bước của lời giải mô phỏng ngây thơ.

Thủ tục nhiều bước cố thực hiện nhiều bước đơn cùng lúc chừng nào: mọi ô không ngập xói ở tốc độ tối đa; mực nước của mọi ô ngập giảm cùng tốc độ; và không ô ngập nào trở thành không ngập trong thời gian ấy. Nó hoạt động như sau:

1. Tính mực nước cho mọi ô.
2. Với mỗi ô, xác định nó có ngập không. Nếu không, tính lượng xói mòn; nếu lượng này không phải \(M\), dừng thủ tục nhiều bước. Để đơn giản, có thể cho ô xói xuống dưới mực biển mà không đổi kết quả.
3. Nếu mọi ô xói với tốc độ \(M\), mực nước mọi “hồ” cũng giảm tốc độ đó. Mỗi hồ có ít nhất một ô biên không ngập quyết định mực hồ, và mức này giảm \(M\). Vì vậy có thể lặp cho tới khi một ô đang ngập nổi lên.
4. Tìm ô ngập có lớp nước phủ mỏng nhất và gộp số bước thích hợp.
5. Nếu không còn ô ngập, tăng số ngày thêm \(\lceil\mathrm{maxheight}/M\rceil\) rồi kết thúc.

Mỗi lần nhiều bước làm một ô ngập được lộ ra; một ô không ngập sẽ không bao giờ ngập lại. Do đó có nhiều nhất \(RC\) lần nhiều bước (thực tế ít hơn vì ô mép bảng không bao giờ ngập).

Để chặn số bước đơn trước một lần nhiều bước, định nghĩa đồ thị phụ có một đỉnh cho mỗi ô không ngập. Với mỗi hồ, gộp mọi ô trong hồ vào một ô biên tùy ý quyết định mực hồ, tức cửa thoát. Hai đỉnh có cạnh tự nhiên nếu có hai ô được gộp vào chúng vốn kề nhau. Chọn “cha” của mỗi đỉnh là một đỉnh kề có mức thấp nhất; ta được một cây gốc tại biển ngoài. Một đường hướng lên cây là cố định nếu chênh cao trên mọi cạnh ít nhất \(M\).

Mỗi ngày, hoặc một ô ngập được lộ ra; hoặc số đỉnh có đường cố định đến gốc tăng; hoặc mọi đỉnh đều nằm trên đường cố định. Trường hợp cuối cho phép thực hiện nhiều bước. Chỉ có tối đa \(RC\) lần tăng trước khi mọi đỉnh cố định, nên trước khi một ô được lộ ra có tối đa \(RC\) bước đơn và một lần nhiều bước. Tổng cộng có tối đa \((RC)^2\) bước đơn và \(RC\) lần nhiều bước, cho thời gian \((RC)^3\log(RC)\). Hằng số rất nhỏ nên chạy kịp.

Để chứng minh khẳng định trên, xét một đường cố định và giả sử phân bố đỉnh không đổi (hồ vẫn là hồ, không ô nào lộ ra). Sau một ngày đường vẫn cố định vì mọi ô trên đó giảm cùng lượng. Lấy một đỉnh chưa thuộc đường cố định nhưng cha của nó đã thuộc. Mực biển theo định nghĩa nằm trên đường cố định; nếu không có đỉnh như vậy thì mọi đỉnh đã cố định. Sau một ngày, đỉnh này giảm xuống mức cũ của cha, còn cha giảm \(M\), tạo chênh lệch đúng \(M\); vậy đỉnh gia nhập đường cố định. Chứng minh hoàn tất.

Cận trên thực ra có thể gần đạt được với \(M=2\). Lấy một đường ngoằn ngoèo dài cỡ \(RC\), không tự chạm:

X X X X X X X
P P P P P P X
X X X X X P X
X P P P P P X
X P X X X X X
X P P P P P X
X X X X X X X

Trong đó X là các giá trị rất lớn và P là đường đi. Trong một thời gian dài, cây nói trên chính là đường duy nhất đánh dấu P.

Đặt trên đường các giá trị

với \(L\) là độ dài đường. Không khó kiểm tra rằng các thay đổi “lệch một” truyền lên đường với tốc độ một, và mỗi thay đổi được truyền hoàn toàn trước khi thay đổi kế tiếp bắt đầu do một hồ khác được lộ ra.

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