Phân tích: Out of Gas

Đây là một bài toán khá khó để nắm bắt ý tưởng ban đầu, như kết quả thi đấu đã cho thấy. Tuy nhiên, giải pháp cuối cùng lại đơn giản một cách đáng ngạc nhiên (mặc dù lập luận cho nó thì không hề đơn giản).

Trước hết, hãy xem xét một trường hợp duy nhất với một giá trị gia tốc \(a\) và \(N\) lớn tùy ý. Giả sử một chiến lược \(S_1\) nào đó đưa bạn về nhà trong thời gian \(T\). Hiển nhiên là \(a \cdot T^2 / 2 \ge D\), vì \(a \cdot T^2 / 2\) là khoảng cách chúng ta đi được nếu bắt đầu tăng tốc ngay lập tức và không bao giờ phanh.

Chúng ta có thể đề xuất một chiến lược thay thế \(S_2\): đầu tiên dừng lại và đợi trong khoảng thời gian \(T - \sqrt{2D/a}\), sau đó bắt đầu tăng tốc hết tốc lực và không bao giờ phanh. Chiến lược này cũng sẽ đưa bạn về nhà tại thời điểm \(T\).

Chúng ta cần chứng minh rằng nếu \(S_1\) không va chạm với xe kia, thì \(S_2\) cũng vậy. Ta chứng minh điều này bằng cách kiểm tra xem \(S_2\) có đến bất kỳ điểm nào giữa đỉnh đồi và nhà bạn sớm hơn \(S_1\) hay không.

Giả sử \(S_1\) ở một điểm \(X\) nào đó muộn hơn \(S_2\). Lưu ý rằng vận tốc của \(S_1\) khi đến \(X\) phải lớn hơn vận tốc của \(S_2\) — nếu không, ngay cả khi tăng tốc hết mức, \(S_1\) cũng không thể đuổi kịp \(S_2\). Nhưng không thể đạt được vận tốc tại \(X\) lớn hơn \(S_2\): chiến lược \(S_2\) đã tăng tốc toàn bộ quãng đường từ đỉnh đồi đến \(X\).

Vì vậy, bây giờ chúng ta chỉ cần xem xét các chiến lược như \(S_2\). Việc cần làm là xác định xem chúng ta cần đợi trên đỉnh đồi trong bao lâu.

Một điều cuối cùng cần lưu ý là nếu xe kia di chuyển với vận tốc không đổi giữa \(x_i\) và \(x_{i+1}\), và chiến lược của chúng ta không khiến chúng ta vượt trước xe kia tại \(x_i\) hoặc \(x_{i+1}\), thì nó cũng sẽ không vượt qua xe kia tại bất kỳ điểm trung gian nào. Chúng ta biết điều đó vì nếu chúng ta vượt qua nó tại một điểm trung gian, điều đó có nghĩa là chúng ta đang di chuyển nhanh hơn xe kia tại thời điểm đó; và vì chúng ta đang tăng tốc, còn vận tốc của xe kia là không đổi, chúng ta chắc chắn sẽ ở phía trước nó tại \(x_{i+1}\). Do đó, việc vượt qua xe kia giữa \(x_i\) và \(x_{i+1}\) dẫn đến mâu thuẫn, và trường hợp đó không thể xảy ra.

Thuật toán

Với lập luận này, chúng ta có hai thuật toán khả thi:

1. Tìm kiếm nhị phân: Để kiểm tra xem thời gian chờ \(T_{wait}\) có đủ lâu hay không, chúng ta chỉ cần kiểm tra tất cả \(N\) điểm mà xe kia có thể thay đổi vận tốc. Để đạt được độ chính xác \(10^{-6}\), chúng ta sẽ cần khoảng 40 lần lặp trong tìm kiếm nhị phân. Điều này giúp giải quyết mỗi bộ thử nghiệm trong thời gian \(O(N \cdot A)\), với hằng số 40 ẩn trong ký hiệu Big-O — đủ nhanh.

2. Duyệt trực tiếp: Nếu lo ngại về hằng số 40, chúng ta có thể duyệt qua tất cả các điểm \(x_i\), và với mỗi điểm, tính toán thời gian chờ tối thiểu cần thiết để không vượt qua xe kia tại điểm đó: \(t_i - \sqrt{2x_i/a}\) cho tất cả \(i\) sao cho \(x_i < D\). Bạn cũng phải bao gồm thời điểm mà xe kia đạt đến vị trí nhà của bạn (tại \(x = D\)). Thời gian chờ tối ưu sẽ là giá trị lớn nhất trong các giá trị này (nhưng không nhỏ hơn 0). Sau đó, thời gian về nhà sẽ là \(T_{wait} + \sqrt{2D/a}\). Cách tiếp cận này giúp giải quyết bài toán trong thời gian \(O(N \cdot A)\) mà không có hằng số lớn.

Độ phức tạp

• Thời gian: \(O(N \cdot A)\) cho mỗi bộ thử nghiệm.
• Không gian: \(O(N)\) để lưu trữ lộ trình của xe phía trước.

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