Test Set 1

Có thể diễn giải bài toán thành việc tìm luồng cực đại chi phí nhỏ nhất trên một cây có hướng. Các điểm nghỉ được biểu diễn bằng các đỉnh, còn các dốc trượt tuyết được biểu diễn bằng các cạnh. Một thuật toán thường dùng cho bài toán luồng cực đại chi phí nhỏ nhất là liên tiếp tìm đường đi ngắn nhất (successive shortest paths). Với cây có hướng trong bài này, ta có thể áp dụng một phiên bản đơn giản hóa của cách tiếp cận đó.

Nhận xét rằng ta có thể thêm người trượt tuyết một cách tham lam. Trong tất cả các đỉnh có thể đi tới từ đỉnh núi (gốc của cây), ta luôn nên đưa một người tới đỉnh có đường đi với chi phí nhỏ nhất, chỉ sử dụng những cạnh vẫn còn sức chứa. Vì đồ thị là một cây, chỉ có đúng một đường đi từ gốc tới mỗi đỉnh. Do đó, ta có thể tính chi phí đường đi tới mọi đỉnh bằng bất kỳ phép duyệt cây nào bắt đầu từ gốc: chi phí tới một đỉnh bằng chi phí tới cha của nó (đã được tính trước) cộng với chi phí của cạnh nối cha với đỉnh đó. Sau đó, sắp xếp các đỉnh theo chi phí đường đi tăng dần. Ta luôn sử dụng đỉnh đầu tiên trong danh sách mà đường đi tới nó vẫn còn một lượng sức chứa dương.

Ta duy trì số người đã được đưa qua mỗi cạnh và lần lượt xét danh sách các đỉnh đã sắp xếp. Với đỉnh hiện tại, kiểm tra các cạnh trên đường đi để biết đường đó còn sức chứa hay không; nếu còn thì cập nhật lượng sức chứa, còn nếu không thì chuyển sang đỉnh tiếp theo trong danh sách. Nếu làm riêng cho một người, thao tác này mất \(O(N)\) thời gian. Tuy nhiên, ta biết rằng mình sẽ tiếp tục dùng cùng đường đi cho tới khi một cạnh nào đó hết sức chứa. Vì vậy, bằng một lượt duyệt tuyến tính trên đường đi, ta có thể tìm lượng sức chứa còn lại nhỏ nhất và mô phỏng việc đưa đồng thời đúng số người đó qua đường đi. Mỗi bước như vậy mất tổng cộng \(O(N)\) thời gian. Vì cần thử tối đa \(O(N)\) đích có thể có, toàn bộ thuật toán chạy trong \(O(N^2)\) thời gian, đủ hiệu quả cho Test Set 1.

Test Set 2

Với dữ liệu lớn, ta cần cải tiến thêm. Có thể dùng phân rã nặng–nhẹ (heavy-light decomposition) trên cây để quản lý sức chứa còn lại của các cạnh. Cấu trúc phân rã phải hỗ trợ cập nhật và truy vấn trên các đường đi từ gốc tới một đỉnh bên trong cây. Mỗi phép cập nhật trừ một lượng khỏi sức chứa của tất cả các cạnh trên đường đi; mỗi phép truy vấn tìm sức chứa nhỏ nhất trong tất cả các cạnh trên đường đi đó.

Phân rã nặng–nhẹ chia cây thành một tập các đường đi đôi một rời nhau sao cho đường từ bất kỳ đỉnh nào tới gốc đi qua nhiều nhất \(O(\log N)\) đường của phép phân rã. Nếu duy trì một cây đoạn cho mỗi đường của phép phân rã, ta có thể thực hiện cả truy vấn lẫn cập nhật trong \(O(\log^2 N)\). Lưu ý rằng cây đoạn phải hỗ trợ cập nhật đoạn bằng kỹ thuật truyền lười. Nhờ đó, mỗi bước của thuật toán cho Test Set 2 chỉ mất \(O(\log^2 N)\) thay vì \(O(N)\). Tổng thời gian của thuật toán là \(O(N \log^2 N)\), đủ để giải Test Set 2.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2020, Virtual World Finals, bài Pack the Slopes; kho Google Coding Competitions (Apache-2.0).