Phân tích: Don't Break The Nile

Chúng ta được cung cấp một lưới (đại diện cho một con sông) kích thước \(W \times H\) chứa các hình chữ nhật rời nhau (đại diện cho các tòa nhà). Mỗi ô trong lưới không bị bao phủ bởi hình chữ nhật có thể duy trì một dòng chảy \(1\) đơn vị nước và nước có thể chảy sang các ô kề cạnh. Các ô bị bao phủ bởi hình chữ nhật không thể duy trì dòng chảy. Tất cả các ô ở phía dưới (phía nam) có dòng chảy ngầm đi vào là \(1\) đơn vị. Bạn cần tìm đơn vị nước tối đa có thể chảy đến các ô ở phía trên (phía bắc).

Cách tiếp cận tham lam

Nếu chúng ta coi một "dòng" nước là một đường dẫn kết nối \(1\) đơn vị từ dưới lên trên, thì bài toán có thể được coi là tìm số lượng tối đa các dòng nước không giao nhau có thể nằm vừa trong lưới. Nếu chúng ta phải tìm từng dòng hợp lệ một, thì việc cố gắng giữ cho dòng nước càng gần biên của bảng càng tốt là hợp lý nhất, vì điều đó để lại nhiều không gian nhất cho các dòng nước trong tương lai.

Áp dụng ý tưởng này vào một thuật toán, chúng ta có thể bắt đầu tại ô trống dưới cùng bên trái nhất, và sử dụng quy tắc bàn tay trái (left-hand-rule) được mô tả tại đây. Về cơ bản, chúng ta đi về phía trước với mục tiêu đạt đến đỉnh, giữ càng sát tường bên trái càng tốt. Hình minh họa dưới đây cho thấy ý tưởng này. Các tòa nhà có màu đen, và các phần có màu khác (đỏ, xanh lá, vàng, xanh dương và tím) là sông. Để dễ hình dung việc đi theo quy tắc bàn tay trái, chúng ta có thể tưởng tượng một bức tường vô hạn ở bên trái và bên phải con sông.

Dòng đầu tiên bắt đầu từ ô trống dưới cùng bên trái nhất, là ô thứ 3 từ bên trái (màu đỏ). Đường dẫn đến đỉnh giữ càng gần tường bên trái càng tốt như các ô màu đỏ. Dòng thứ hai là các ô màu xanh lá cây. Nó đi lên, sang trái và quay lại (vì là ngõ cụt) và tiếp tục sang phải, giữ càng gần tường bên trái càng tốt. Dòng thứ ba là các ô màu vàng. Và cuối cùng, dòng thứ tư là các ô màu tím không thể chạm tới đỉnh.

Độ phức tạp thời gian là \(O(WH)\), đủ nhanh cho dữ liệu nhỏ nhưng không đủ cho dữ liệu lớn. Có những mẹo để mở rộng quy mô này cho dữ liệu lớn, ví dụ: chúng ta có thể sử dụng nén tọa độ, nhưng việc cài đặt chính xác có thể rất phức tạp. Do đó, trong các phần sau, chúng ta sẽ mô tả các cách tiếp cận thay thế.

Luồng cực đại (Maximum Flow)

Đề bài gợi ý rằng đây là một bài toán luồng cực đại trong đó các ô là các đỉnh trong đồ thị. Mỗi đỉnh có dung lượng = \(1\) nếu ô đó không bị tòa nhà bao phủ, ngược lại dung lượng của đỉnh bằng \(0\). Các cạnh giữa các đỉnh kề nhau có thể có dung lượng vô hạn. Chúng ta có thể kết nối tất cả các ô ở phía dưới với một đỉnh mới gọi là nguồn (source) với dung lượng cạnh vô hạn. Tương tự, chúng ta có thể kết nối tất cả các ô ở phía trên với một đỉnh mới gọi là đích (sink). Sau đó, chúng ta tìm luồng cực đại từ nguồn đến đích.

Với mô hình đồ thị này, có thể giải quyết dữ liệu nhỏ nơi số lượng cạnh tối đa là \(4 \times W \times H = 4 \times 100 \times 500 = 200,000\) và luồng cực đại \(f\) tối đa là \(W = 100\). Nếu chúng ta sử dụng phương pháp Ford-Fulkerson có độ phức tạp \(O(Ef)\), mỗi bộ thử nghiệm nhỏ chỉ yêu cầu tối đa 20 triệu phép tính. Tuy nhiên, điều này vẫn không đủ để giải quyết dữ liệu lớn (thực tế, cách này chậm hơn giải pháp tham lam).

Lát cắt tối tiểu (Minimum Cut)

Để giải quyết dữ liệu lớn, chúng ta cần nhìn bài toán từ một góc độ khác. Theo định lý luồng cực đại - lát cắt tối tiểu, luồng cực đại từ nguồn đến đích bằng với dung lượng tối thiểu (hoặc dung lượng đỉnh trong trường hợp của chúng ta) cần được loại bỏ (cắt) khỏi đồ thị để không có luồng nào có thể đi từ nguồn đến đích. Hóa ra đối với bài toán này, việc tìm lát cắt tối tiểu dễ dàng hơn tìm luồng cực đại. Tức là, chúng ta cần xác định số lượng ô (đỉnh) tối thiểu cần loại bỏ để nguồn bị ngắt kết nối khỏi đích.

Hãy nhìn vào ví dụ trên. Hình bên trái cho thấy một con sông không có tòa nhà nào. Nguồn được kết nối với tất cả các ô ở phía dưới và đích được kết nối với tất cả các ô ở phía trên. Luồng cực đại từ nguồn đến đích là 5. Nhìn vào cấu trúc của con sông, rõ ràng là để tạo ra một lát cắt hợp lệ (thông qua việc loại bỏ các ô) ngắt kết nối nguồn và đích, lát cắt phải tạo thành một đường dẫn từ phía bên trái của con sông sang phía bên phải của con sông. Hình bên phải cho thấy giải pháp lát cắt tối tiểu nơi chúng ta loại bỏ các ô (được đánh dấu màu vàng) để cắt con sông từ trái sang phải sao cho nguồn hiện đã bị ngắt kết nối khỏi đích. Quan sát thấy rằng lát cắt tối tiểu (số lượng ô bị loại bỏ) bằng với luồng cực đại.

Bây giờ, hãy xem các ví dụ có tòa nhà. Vì các ô bị tòa nhà bao phủ hoạt động giống như các ô bị loại bỏ (chúng không cho phép nước chảy qua), chúng ta có thể tận dụng các tòa nhà để giảm thiểu số lượng ô cần loại bỏ để tạo ra một lát cắt hợp lệ.

Hình bên trái cho thấy một con sông với một tòa nhà ở giữa. Để ngắt kết nối nguồn khỏi đích, chúng ta chỉ cần loại bỏ thêm hai ô: một ô kết nối phía bên trái sông với phía bên trái tòa nhà (màu đỏ), và một ô khác kết nối phía bên phải tòa nhà với phía bên phải sông (màu vàng). Do đó, lát cắt tối tiểu (và do đó là luồng cực đại) của đồ thị này là 2.

Lát cắt tối tiểu dưới dạng đường đi ngắn nhất

Với những hiểu biết trên, chúng ta có thể diễn đạt lại bài toán như sau: tìm đường đi ngắn nhất từ phía bên trái sông sang phía bên phải sông trong đó các đỉnh là các tòa nhà và chi phí cạnh giữa hai tòa nhà là khoảng cách ngắn nhất giữa chúng. Lưu ý rằng khoảng cách ngắn nhất giữa hai tòa nhà là số lượng ô chúng ta cần loại bỏ để cắt đứt vùng giữa hai tòa nhà đó.

Các ô màu đỏ cho thấy các đường đi ngắn nhất từ phía bên trái sông đến ba tòa nhà, trong khi các ô màu vàng cho thấy các đường đi ngắn nhất từ phía bên phải sông đến các tòa nhà. Các ô màu xanh lá cây cho thấy khoảng cách từ tòa nhà này đến tòa nhà khác, ví dụ: khoảng cách giữa tòa nhà A và B là 4.

Trong ví dụ trên, lát cắt tối tiểu được hình thành bởi đường đi ngắn nhất từ phía bên trái sông đến A (khoảng cách 2), sau đó từ A đến B (khoảng cách 4), rồi từ B đến phía bên phải sông (khoảng cách 5). Như vậy, số lượng ô tối thiểu (lát cắt tối tiểu) cần loại bỏ để ngắt kết nối nguồn và đích là 11 ô, bằng với luồng cực đại.

Để tính khoảng cách giữa hai tòa nhà, chỉ cần xem xét khoảng cách (gap) của chúng theo hướng ngang hoặc hướng dọc, và lấy giá trị lớn nhất trong hai giá trị đó. Khoảng cách ngang về cơ bản là khoảng cách nhỏ nhất giữa hai tòa nhà nếu bạn chiếu hai tòa nhà lên trục ngang (x) (tương tự cho trục dọc). Ví dụ, tòa nhà A và B có khoảng cách dọc là 2 đơn vị và khoảng cách ngang là 4 đơn vị. Khoảng cách từ A đến B là giá trị lớn hơn (tức là 4). Lưu ý rằng khoảng cách dọc giữa A và C là 0 vì chúng chồng lấn nhau khi chiếu lên trục dọc (y).

Khi tính toán khoảng cách, chúng ta có thể coi phía bên trái và phía bên phải cũng là các tòa nhà (với chiều cao vô hạn). Đối với chúng, chúng ta chỉ tính khoảng cách ngang và bỏ qua khoảng cách dọc.

Một người có thể thắc mắc về trường hợp có một tòa nhà khác nằm giữa hai tòa nhà bất kỳ. Điều đó có nghĩa là khoảng cách thực tế giữa hai tòa nhà có thể ngắn hơn (bằng cách tận dụng tòa nhà ở giữa). Điều này xảy ra khi chúng ta nhìn vào khoảng cách giữa A và C. Khoảng cách trực tiếp giữa A và C là 9 nhưng do có tòa nhà B, khoảng cách giảm xuống còn 8 (tổng khoảng cách từ A đến B và từ B đến C). Vì chúng ta chạy thuật toán đường đi ngắn nhất tiêu chuẩn, nó sẽ tự động tận dụng các tòa nhà ở giữa.

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