Code Jam 2008 - Chung kết Thế giới

Phân tích: Bridge Builders

Bài toán này thoạt nhìn có vẻ đáng sợ. Có rất nhiều tuyến đường khác nhau giữa các đảo, và cách tính chi phí hơi thiếu trực quan. Tuy nhiên, thực chất bài toán là một bài Cây khung nhỏ nhất (Minimum Spanning Tree, MST) giữa các khu rừng được ngụy trang; điều hay ở MST là chúng rất phù hợp với các cách tiếp cận tham lam. Hầu như mọi chiến lược tham lam hợp lý tập trung vào việc nối các khu rừng đều cho đáp án đúng.

Khá dễ để tự thuyết phục rằng cách đúng cho bộ dữ liệu Nhỏ là đi thẳng về phía khu rừng bên kia; việc này không thể gây bất lợi, vì mọi đảo khác đều trả chi phí nhỏ nhất có thể của nó (tức khoảng cách đến khu rừng gần nhất). Thực ra, giả sử các đảo trả chi phí nhỏ nhất chính là mấu chốt: ta có thể bỏ qua chi phí “cơ sở” này, và khi đó thời điểm duy nhất ta thực sự phải trả phần “phụ trội” là lúc nối hai khu rừng.

Vì vậy, với bộ dữ liệu Lớn, một lần nữa ta bỏ qua chi phí “cơ sở” của từng đảo và chỉ tập trung đi đến tất cả các khu rừng; đạt được điều đó là xong. Từ trực giác này, ta có thể nghĩ ngay đến việc xây một MST trên các khu rừng. Chi phí “phụ trội” để nối các khu rừng tăng theo khoảng cách, nên hãy dùng thuật toán Prim: luôn đi về khu rừng gần nhất với các khu rừng đã thăm. Sau khi nối tất cả các khu rừng, ta có thể xây các cầu có chi phí tối thiểu đến những đảo còn lại.

Cách tham lam này luôn đúng và khá trực quan khi nhìn bài toán theo cách trên. Tuy nhiên, chứng minh tính đúng đắn lại khá kỹ thuật. Ta phải chắc chắn rằng các kết nối giữa rừng thật sự tạo thành một đồ thị có chi phí được xác định rõ và không phụ thuộc thứ tự. Nếu việc chọn đường đi giữa một cặp rừng bằng cách nào đó có thể giúp tiết kiệm chi phí về sau, lập luận trên sẽ sai (và bóng ma NP-đầy đủ sẽ hiện ra đầy đe dọa). Sau khi tự thử vài ví dụ, việc đó có vẻ hợp lý là không thể xảy ra. Nhưng viết được chứng minh trong thời gian thi có lẽ là bất khả thi. Thực tế, chúng tôi đã phải cộng tác trong vài ngày mới tìm ra một chứng minh đúng đắn, hoàn chỉnh. 🙂 Đó là điều một thí sinh ở Chung kết Google Code Jam phải đối mặt!

Sau đây là phác thảo chứng minh.

Trước hết, giả sử ta đã có một cây (không có chu trình) gồm các cầu nối mọi đảo. Ta sẽ chứng minh cách rẻ nhất để xây các cầu này chính là cách do thuật toán MST của ta đưa ra (trong đó khoảng cách được đo dọc theo cây đã cho). Giả sử ta có một thứ tự xây cầu rẻ nhất nào đó. Đầu tiên, không làm tăng chi phí, ta có thể sắp xếp lại để thứ tự ấy gồm các đường đi trực tiếp, liên tiếp từ một đảo đã thăm trước đó đến một khu rừng. Bây giờ giả sử có lúc từ đảo \(A\) ta xây hai cầu \(A-B\) và \(A-C\). Hơn nữa, giả sử \(A-B\) dẫn đến một đảo gần hơn \(A-C\), nhưng ta lại xây \(A-C\) trước. Cuối cùng, giả sử đây là lần cuối cùng xảy ra tình huống như vậy; do đó trong cây con của \(B\) và cây con của \(C\), ta xây trực tiếp về phía các đảo gần nhất.

Gọi \(w\) là khoảng cách, tại thời điểm xây \(A-C\), từ \(A\) đến khu rừng gần nhất của nó dọc theo các cầu đã xây. Gọi \(x\) là khoảng cách ấy tại thời điểm xây \(A-B\) (nên \(x \le w\)). Gọi \(y\) là khoảng cách từ \(A\) đến đảo gần nhất trong cây con của \(B\), và \(z\) là khoảng cách đến đảo gần nhất trong cây con của \(C\) (nên \(y \le z\)). Khi đó chi phí xây các đường \(A-C\) và \(A-B\) là

Thay vào đó, nếu xây đường \(A-B\) trước, còn \(A-C\) và cây con của nó để lại sau, ta trả nhiều nhất

và có thể còn ít hơn vì các bước trung gian cũng có thể rẻ hơn. Lấy biểu thức thứ nhất trừ biểu thức thứ hai, ta được

là một số không âm.

Do đó, không làm tăng chi phí, ta có thể đổi thứ tự để xây \(A-B\) trước. Lặp lại phép biến đổi này, ta suy ra rằng có một cách rẻ nhất để xây cây cầu luôn đi về khu rừng gần nhất trước, đúng như thuật toán của ta.

Bây giờ, với một đồ thị bất kỳ (một tập đảo cùng một tập các cầu có thể xây), ta chứng minh quy nạp rằng thuật toán luôn cho chi phí nhỏ nhất. Điều này đúng với 1 đảo; giả sử đúng với \(k\) đảo. Xét một phương án tối ưu nối \(k+1\) đảo. Gọi \(A-B\) là cây cầu được xây cuối cùng. \(B\) không thể đã được thăm trước đó; vì thế hãy xét phương án này khi giới hạn trên \(k\) đảo đầu. Theo giả thuyết quy nạp, phương án ấy không thể rẻ hơn thuật toán của ta chạy trên \(k\) đảo đó; hơn nữa — một tính chất hay của thuật toán mà có thể bạn chưa nhận thấy — sau khi chạy thuật toán, \(A\) ở gần một khu rừng nhất có thể. Vì vậy, làm như thế rồi xây \(A-B\) cũng là một phương án rẻ nhất và, quan trọng hơn, nó tạo thành một cây cầu. Gọi cây này là \(T\).

Theo phần trên, ta đã biết chi phí xây cây cầu này: đó chính là tổng chi phí khi chạy thuật toán trên các khoảng cách rừng-đến-rừng trong \(T\). Nhưng các khoảng cách ấy ít nhất cũng lớn bằng những khoảng cách rừng-đến-rừng tương ứng khi được phép dùng tất cả các cầu tiềm năng giữa \(k+1\) đảo. Ta đã trả ít nhất bằng một cây khung thông thường trên các khu rừng — do đó ít nhất bằng một MST. Mà thuật toán của ta đạt đúng chi phí MST này, nên giờ ta biết nó là tối thiểu.

Điều phải chứng minh.

Điều thú vị là kết quả này đúng với mọi đồ thị gồm các đảo và các cầu tiềm năng, không chỉ lưới hay đồ thị phẳng. Hàm biến khoảng cách thành chi phí cũng có thể là bất kỳ hàm không giảm nào. Những đặc điểm đó trong đề bài là nhân tạo và không thiết yếu đối với thuật toán.

Cuối cùng, dưới đây là mã giả cho lời giải, giả sử bạn đã biết một thuật toán MST chuẩn.

for each unordered pair of forests (a, b)
  x = distance(a, b)
  y = x / 2  // Assume integer division
  c = x * (x + 1) / 2  // Add cost of connecting forests
  c -= y * (y + 1)  // Subtract "base" cost of islands
  if x is even
    c += y // Avoid double-counting middle island
  add edge (a, b) at cost c to forest_graph

result = min_cost_spanning_tree(forest_graph)

for each island x
  d = INFINITY
  for each forest y
    d = min(d, distance(x, y))
  result += d  // Add "base" cost of island x

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