Phân tích: Can't Stop

Chia để trị

Có một giải pháp chia để trị khá hay. Chia dữ liệu đầu vào làm đôi; khoảng tốt nhất hoặc nằm hoàn toàn ở nửa bên trái, hoặc nằm hoàn toàn ở nửa bên phải, hoặc đi ngang qua điểm giữa. Chúng ta xử lý các trường hợp trái và phải bằng đệ quy; nếu chúng ta có thể xử lý trường hợp "đi ngang qua" trong thời gian tuyến tính, chúng ta sẽ có thuật toán \(O(N \log N)\), đủ tốt để vượt qua giới hạn.

Nếu khoảng tốt nhất đi ngang qua điểm giữa, chúng ta biết nó phải sử dụng phần tử ở giữa, vì vậy chúng ta phải chọn một trong \(D\) số trong bộ tung đó để sử dụng. Bây giờ đi xa nhất có thể sang trái và phải với số đó. Khi dừng lại, chúng ta có thể mở rộng sang trái hoặc sang phải, vì vậy có \(2D\) số khác nhau để thử chọn làm số thứ hai. Mở rộng một lần nữa, và nhận được thêm \(2D\) số nữa để thử cho lần mở rộng cuối cùng (với \(k=3\)). Tổng cộng, chúng ta chỉ thử \(D \times 2D \times 2D\) lựa chọn khác nhau, vì vậy toàn bộ quá trình xử lý điểm giữa chạy trong thời gian \(256N\), và chúng ta có thuật toán thời gian \(O(N \log N)\).

Lưu ý: Một điều đáng ngạc nhiên đối với thuật toán chia để trị là chúng ta không sử dụng bất kỳ thông tin nào từ các nửa trái và phải để giải quyết trường hợp ở giữa; chỉ riêng việc nó đi qua điểm giữa là đủ.

Cách tiếp cận chậm và đơn giản

Có một nhóm các cách tiếp cận khác cho bài toán này. Thử mọi vị trí bắt đầu, mở rộng ra bên phải và chỉ đưa ra lựa chọn khi cần thiết (giống như trong chia để trị). Cách này tốn \(O(D^k \times N)\) cho mỗi vị trí bắt đầu, hoặc tổng cộng là \(O(D^k \times N^2)\), quá chậm. Tuy nhiên, có một vài cải tiến khác nhau (một số nhỏ, một số lớn) mà người ta có thể thực hiện để làm cho nó trở nên tuyến tính theo \(N\).

Thời gian tuyến tính

Một cải tiến hoạt động theo cách này: Mỗi khi bạn chọn một số, hãy kiểm tra xem bộ tung ngay trước vị trí bắt đầu của bạn có chứa số đó hay không. Nếu có, chúng ta có thể bỏ qua lựa chọn đó một cách an toàn (vì chúng ta sẽ đạt được kết quả tốt hơn nếu bắt đầu sớm hơn một bộ tung và chọn cùng một tập hợp các số đó).

Hóa ra cách này chạy trong thời gian tuyến tính, nhưng lý do tại sao thì không hiển nhiên. Chúng ta muốn chứng minh rằng một chỉ số \(i\) cụ thể chỉ được truy cập từ \(O(1)\) vị trí bắt đầu. Hãy tưởng tượng chúng ta đã đến được \(i\) từ vị trí start. Bây giờ hãy tưởng tượng bắt đầu tại \(i\) và đi ngược về phía trái (như thường lệ, chúng ta mở rộng về phía trái xa nhất có thể trước khi chọn mỗi số mới). Nếu chúng ta chỉ chọn các số từ tập hợp đã đưa chúng ta từ start đến \(i\), chúng ta chắc chắn phải quay lại được start (và không xa hơn, vì tối ưu hóa ở trên đảm bảo rằng start - 1 không chứa bất kỳ số nào trong tập hợp của chúng ta). Nhưng chỉ có \(1 + D + D^2 + D^3\) lựa chọn số khác nhau bắt đầu từ \(i\), vì vậy chỉ có bấy nhiêu vị trí khả thi cho start, do đó \(i\) sẽ chỉ được truy cập \(O(D^3)\) lần.

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