Phân tích: Airport Walkways

Một số người sẽ nói rằng các bài thi lập trình tuy thú vị để suy nghĩ nhưng không có ứng dụng thực tế. Sau khi giải bài này, bạn có thể cười họ khi mình kịp chuyến bay còn họ vẫn phải xếp hàng ở sân bay cùng những người kém may mắn khác.

Một điều quan trọng cần nhận thấy trong bài toán này là vị trí của các băng chuyền không quan trọng, vì bạn có thể chuyển đổi tức thì giữa các tốc độ khác nhau. Điều này có nghĩa là hai băng chuyền có tốc độ \(v\) với chiều dài \(L_1\) và \(L_2\) có thể được kết hợp thành một băng chuyền duy nhất có chiều dài \(L_1 + L_2\) với tốc độ \(v\). Bằng cách kết hợp điều này với quan sát rằng bất kỳ phần hành lang nào không có băng chuyền đều tương đương với một băng chuyền có \(v = 0\), bạn có thể đưa bài toán về việc có các băng chuyền với các tốc độ khác nhau và độ dài biến đổi, sau đó quyết định cho mỗi băng chuyền nên chạy hay đi bộ (hoặc mỗi thứ một phần).

Tập dữ liệu nhỏ có thể được giải quyết bằng phương pháp duyệt (brute force). Gọi \(W\) là tập hợp tất cả các băng chuyền có chiều dài dương (mỗi băng chuyền có một tốc độ duy nhất). Vì chỉ có \(|W| \le 21\) loại tốc độ băng chuyền khác nhau cần xem xét, bạn có thể thử chọn từng tập con \(S \subseteq W\) để chạy (và đi bộ trên phần còn lại, \(W - S\)). Giải pháp này hơi phức tạp ở chỗ khi bạn đã chọn \(S\), bạn vẫn phải quyết định băng chuyền nào chỉ chạy một phần, trong trường hợp bạn không có đủ thời gian để chạy hết tất cả. Tuy nhiên, bạn lại có thể duyệt quyết định này bằng cách lặp qua từng băng chuyền \(x \in S\) và chỉ chạy trên băng chuyền \(x\) với thời gian còn lại sau khi đã chạy hết các băng chuyền trong \(S - \{x\}\). Bạn chỉ cần lấy giá trị nhỏ nhất trong tất cả các lựa chọn, loại bỏ bất kỳ lựa chọn nào yêu cầu thời gian chạy nhiều hơn \(t\) giây. Điều này có thể được cài đặt trong \(O(N^2 \cdot 2^N)\) và sẽ chạy kịp với \(N\) tối đa là 20.
Thử thách thêm: Cài đặt thuật toán này trong thời gian \(O(N \cdot 2^N)\).

Tuy nhiên, cách tiếp cận này sẽ bị quá thời gian đối với tập dữ liệu lớn, nơi \(N\) lên đến 1000. Đối với trường hợp này, chúng ta cần một cách tốt hơn để quyết định khi nào nên chạy và khi nào nên đi bộ. Chúng ta chỉ cần quyết định xem chạy trên băng chuyền chậm hay nhanh thì tốt hơn. Hóa ra chúng ta có thể giải quyết vấn đề này bằng một thuật toán tham lam đơn giản, và chúng ta có thể chứng minh nó là tối ưu bằng cách sử dụng lập luận trao đổi (exchange argument).

Giả sử chúng ta có hai băng chuyền bất kỳ với tốc độ \(w_1\) và \(w_2\), với \(w_1 < w_2\). Bây giờ giả sử trong một thuật toán nào đó, chúng ta đã quyết định chạy trong \(r_1\) và \(r_2\) giây trên mỗi băng chuyền tương ứng. Nếu \(s_1\) và \(s_2\) là lượng thời gian chúng ta đi bộ trên mỗi băng chuyền, thì tổng thời gian sẽ là \(T = r_1 + s_1 + r_2 + s_2\) giây. Điều gì sẽ xảy ra nếu thay vào đó chúng ta quyết định chạy trong \(r_1 + \epsilon\) giây trên băng chuyền thứ nhất và \(r_2 - \epsilon\) giây trên băng chuyền thứ hai, với \(\epsilon > 0\)? Khi đó tổng thời gian sẽ là \(T' = (r_1 + \epsilon) + s_1' + (r_2 - \epsilon) + s_2'\) giây. Giải phương trình cho \(T - T'\), bạn sẽ nhận được \(\epsilon \cdot (w_2 - w_1) \cdot (R - S) / ((w_1 + S) \cdot (w_2 + S)) > 0\), điều này cho thấy \(T > T'\), và do đó sự thay đổi sẽ luôn có lợi. Nói một cách đơn giản, luôn luôn tốt hơn nếu chạy trên các băng chuyền chậm nhất có thể.

Lưu ý rằng một số chi tiết của các phương trình trên đã được lược khỏi bản phân tích chính thức và được dành lại như một bài tập cho người đọc.

Dưới đây là mã nguồn Java đơn giản để giải quyết bài toán:

double res=0;
for (int i=0; i<=100; ++i) {
  double runTime=Math.min(t,W[i]/(i+R));
  double walkDist=W[i]-runTime*(i+R);
  double walkTime=walkDist/(i+S);
  res+=runTime+walkTime;
  t-=runTime;
}
System.out.printf("Case #%d: %.12f%n",TC,res);

Độ phức tạp:

• Sắp xếp các băng chuyền theo tốc độ: \(O(N \log N)\).
• Duyệt qua các băng chuyền để tính toán thời gian: \(O(N)\).
• Tổng độ phức tạp: \(O(N \log N)\).

Thử thách thêm: Giải bài toán nếu các giới hạn thay đổi thành \(1 \le w_i \le 10^9\).

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