Phân tích: Bus Stops

Bài toán này có thể được giải quyết bằng cách sử dụng quy hoạch động và nhân ma trận để giải các dãy truy hồi tuyến tính.

Xét một cấu hình các xe buýt nằm trong một cửa sổ có độ rộng \(P\) và đẩy xe buýt ở vị trí ngoài cùng bên trái tiến lên sao cho tất cả các xe buýt vẫn nằm trong một cửa sổ (đã dịch chuyển) có độ rộng \(P\).

Bây giờ chúng ta có thể định nghĩa một trạng thái là vị trí của các xe buýt trong phạm vi \(P\) đơn vị. Ví dụ: nếu chúng ta có \(P = 10\) và \(K = 5\) xe buýt, thì chúng ta có \(252\) trạng thái khả thi (\(\binom{10}{5}\)). Gọi \(NS\) là số lượng trạng thái.
Để đảm bảo chúng ta không đếm cùng một trạng thái trong các cửa sổ khác nhau, chúng ta có thể yêu cầu luôn có một xe buýt ở vị trí ngoài cùng bên trái trong cửa sổ.

Để tiến cửa sổ kích thước \(P\), chúng ta di chuyển xe buýt ở vị trí ngoài cùng bên trái. Luôn có một xe buýt ở đó. Bây giờ hãy nhớ rằng trạng thái mới phải có một xe buýt ở vị trí ngoài cùng bên trái, vì vậy cửa sổ có thể di chuyển sang phải nhiều hơn một vị trí.

Chúng ta tính toán tất cả các chuyển trạng thái có thể. Gọi \(C\) là ma trận chuyển trạng thái, trong đó \(C_{a,b}\) là số cách chúng ta có thể đi từ trạng thái \(a\) sang trạng thái \(b\).
Với mỗi trạng thái \(j\), với cửa sổ ở vị trí \(i\), chúng ta sẽ có dạng:

A[Sj][i+1] = C1,jA[S1][i] + C2,jA[S2][i] + ... + CNS,jA[SNS][i]

\(A[s][p]\) là số cách chúng ta có thể đạt đến trạng thái \(s\) khi cửa sổ ở vị trí \(p\).

Điều này là đủ để giải quyết Small input. Đối với Large input, chúng ta cần tăng tốc độ, vì vậy chúng ta sẽ tính toán hệ thức truy hồi tuyến tính bậc \(NS\) đó bằng cách sử dụng nhân ma trận. Hãy nhìn vào một ví dụ đơn giản hơn về dãy truy hồi tuyến tính - số Fibonacci.

FN = FN-1 + FN-2

Điều này có thể được viết lại thành:

(1 0) * (FN-2) = (FN-1)
(1 1)   (FN-1)   (FN  )

Dưới dạng ngắn gọn hơn, chúng ta có:

M * VN-1 = VN

Điều này nói rằng để tính \(V_N = (F_N, F_{N-1})\) từ \(V_{N-1} = (F_{N-2}, F_{N-1})\), chúng ta cần nhân với \(M\). Bây giờ chúng ta có thể áp dụng điều này một cách đệ quy:

MX * V0 = VX

\(M^X\) có thể được tính toán bằng thuật toán lũy thừa nhị phân (successive squaring) trong thời gian logarit theo \(X\).

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