Phân tích

Mới nhìn qua, bài toán này có vẻ là một bài mô phỏng đơn giản: liên tục thêm các nhóm vào cho đến khi hết chỗ trên tàu lượn (hoặc hết các nhóm trong hàng đợi), sau đó sắp xếp lại hàng đợi và bắt đầu lại. Lặp lại việc này \(R\) lần là xong.

Đối với bộ dữ liệu Small, cách tiếp cận này là đủ; tuy nhiên với bộ dữ liệu Large, các giới hạn rất lớn — lên tới \(1000\) nhóm xếp hàng cho \(10^9\) lượt chạy — bạn cần một thuật toán thông minh hơn, vì cách mô phỏng trực tiếp có độ phức tạp \(O(N \cdot R)\).

Tối ưu hóa 1

Khi tàu lượn chạy tới \(10^9\) lần, chắc chắn sẽ có một số lượt chạy giống hệt nhau. Nếu bạn lưu trữ hàng đợi các nhóm dưới dạng một mảng cố định và sử dụng một con trỏ trỏ vào vị trí đầu hàng, thì mỗi khi bạn thực hiện một lượt chạy \(s\), bạn có thể ghi lại lượt đó kết thúc ở đâu dựa trên vị trí bắt đầu. Lần tới khi gặp một lượt chạy bắt đầu với cùng một nhóm đó ở đầu hàng, bạn có thể tra cứu nhanh thay vì phải duyệt qua tất cả các nhóm.

Điều này giúp tăng tốc thuật toán lên khoảng \(10^3\) lần trong trường hợp xấu nhất, đưa độ phức tạp về \(O(R)\). Có một số cách khác để tăng tốc tính toán cho mỗi lượt chạy: ví dụ, bạn có thể tạo một mảng tiền tố để tính tổng số người trong đoạn \([group\_a, group\_b]\) trong \(O(1)\), sau đó sử dụng tìm kiếm nhị phân để xác định có bao nhiêu nhóm được đi trong \(O(\log N)\). Tổng cộng sẽ là \(O(R \log N)\) thao tác.

Tối ưu hóa 2

Như đã quan sát ở Tối ưu hóa 1, chúng ta sẽ thấy sự lặp lại giữa các lượt chạy. Bạn cũng sẽ thấy sự lặp lại giữa các chu kỳ của các lượt chạy. Trong ví dụ của đề bài, hàng đợi gồm các nhóm kích thước \([1, 4, 2, 1]\), sức chứa \(k=6\). Hãy xem hàng đợi thay đổi như thế nào giữa các lượt:

1, 4, 2, 1  [5]
2, 1, 1, 4  [4]
4, 2, 1, 1  [6]
1, 1, 4, 2  [6]
2, 1, 1, 4  [4]
4, 2, 1, 1  [6]
1, 1, 4, 2  [6]

Như bạn có thể thấy, có một chu kỳ độ dài 3: bắt đầu từ lượt chạy thứ hai, cứ mỗi 3 lượt chạy thì trạng thái hàng đợi lại giống nhau. Chúng ta kiếm được 16 Euro trong mỗi chu kỳ đó, nghĩa là chúng ta sẽ kiếm được 16 Euro cho mỗi 3 lượt chạy cho đến khi tàu dừng.

Vì vậy, nếu tàu chạy \(10^9\) lần: lượt đầu tiên kiếm được 5 Euro; còn lại \(999,999,999\) lượt; và mỗi cụm 3 lượt này kiếm được 16 Euro. Vì 3 chia hết cho \(999,999,999\) (nếu không chia hết, chúng ta chỉ cần tính toán thêm một vài lượt lẻ ở cuối), tổng số tiền kiếm được là \(5 + (999,999,999 / 3 \times 16) = 5,333,333,333\) Euro.

Một chu kỳ chắc chắn sẽ xuất hiện trong vòng \(N+1\) lượt chạy đầu tiên, vì chỉ có \(N\) trạng thái khác nhau mà hàng đợi có thể bắt đầu (sau \(N\) lượt, bạn buộc phải lặp lại). Do đó, bạn chỉ cần mô phỏng \(N\) lượt chạy, mỗi lượt mất tối đa \(O(N)\) để tìm ra chu kỳ: đây là giải pháp \(O(N^2)\).

Tối ưu hóa 3

Một trong hai tối ưu hóa trên là đủ để vượt qua bài toán. Nhưng nếu bạn muốn tối ưu hơn nữa, bạn có thể kết hợp tìm kiếm nhị phân (như ở Tối ưu hóa 1) với phát hiện chu kỳ (ở Tối ưu hóa 2), đưa thời gian chạy xuống \(O(N \log N)\). Một cách tối ưu hóa khác có thể đưa độ phức tạp xuống \(O(N)\).

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