Phân tích

Trong bài toán thú vị này, có hai góc nhìn mà người ta có thể bắt đầu:

1. Vị trí hiện tại được cố định và mảng các lá bài sẽ xoay vòng mỗi lần.
2. Coi các lá bài như một vòng tròn cố định (được biểu diễn bằng một mảng) và vị trí hiện tại đang được chú ý là một con trỏ di chuyển trên vòng tròn đó.

Đối với hầu hết chúng ta (và các chương trình của chúng ta), việc áp dụng góc nhìn thứ hai sẽ thuận tiện hơn.

Sau khi đọc đề bài, không khó để thấy nhiệm vụ đã rõ ràng: đặt lá bài 1 vào vị trí đầu tiên, sau đó đối với mỗi lá bài \(i\) (theo thứ tự \(2, 3, \dots, K\)), chúng ta bắt đầu từ vị trí hiện tại, và tìm vị trí trống thứ \(i\) về phía bên phải, quay vòng bao nhiêu lần tùy ý, sau đó đặt lá bài \(i\) vào đó.

Vấn đề là mô phỏng quá trình được mô tả ở trên. Điều làm cho nó trở nên thú vị là \(K\) có thể lớn tới \(1000000\), khiến cho việc mô phỏng ngây thơ \(\Theta(K^2)\) trở nên quá chậm so với giới hạn thời gian 8 phút của cuộc thi. Đối với mỗi bước, chúng ta cần tính toán vị trí tiếp theo nhanh hơn nhiều so với \(\Theta(K)\) như trong cách tiếp cận ngây thơ. Chúng tôi mô tả ba giải pháp dưới đây.

Giải pháp A

Gọi \(S = \sqrt{K}\), chúng ta chia \(K\) vị trí thành \(S\) khoảng có kích thước xấp xỉ bằng nhau (cũng là \(S\)). Ngoài việc ghi chép xem vị trí nào đã bị chiếm (một mảng kích thước \(K\), chúng ta gọi là bộ đếm cấp một), chúng ta cũng đếm cho mỗi khoảng có bao nhiêu vị trí đã bị chiếm (một mảng kích thước \(S\) mà chúng ta gọi là bộ đếm cấp hai).

Với thông tin này, chúng ta có thể bỏ qua các khoảng có độ dài \(S\) nhiều nhất có thể, cho đến khi chúng ta đến một khoảng mà chúng ta biết lá bài phải thuộc về. Sau đó, trong khoảng đó, chúng ta chỉ cần xử lý tối đa \(S\) bộ đếm cấp một.

Khi chúng ta đặt một lá bài xuống, việc cập nhật các bộ đếm là một vấn đề đơn giản. Chúng ta chỉ cần cập nhật một bộ đếm ở cấp một và một bộ đếm ở cấp hai.

Giải pháp này chạy trong thời gian \(O(K^{1.5})\).

Giải pháp B

Đẩy mạnh ý tưởng trong giải pháp trước đó. Tại sao không có nhiều cấp độ đếm hơn?
Thực tế, một kế hoạch hay là tổ chức các cấp độ thành một cây nhị phân. Ở cấp độ dưới cùng (cấp một) của cây, chúng ta có mỗi vị trí là một khoảng riêng biệt. Mỗi khi chúng ta lên một cấp, chúng ta kết hợp mỗi khoảng với khoảng kế tiếp. Do đó, chúng ta sẽ có \(\log K\) cấp độ; cấp độ trên cùng là một khoảng duy nhất chứa tất cả các vị trí. Chúng tôi lược bỏ các chi tiết ở đây, vì chúng ta sẽ gặp lại điều này trong phần phân tích của một bài toán ở Round 1C.

Chúng tôi đề cập rằng tổng số bộ đếm là \(O(K)\), và đối với mỗi lá bài, chúng ta sẽ cần thời gian \(O(\log K)\) để tìm vị trí và thêm \(O(\log K)\) thời gian để cập nhật các bộ đếm. Thời gian chạy của phương pháp này là \(O(K \log K)\).

Để biết thêm các ý tưởng tương tự trong khoa học máy tính, bạn có thể tham khảo trang Wiki về cây đoạn (interval tree).

Giải pháp C

Bây giờ chúng ta hãy làm điều gì đó khác biệt. Tại mỗi bước, sau khi một vị trí bị chiếm bởi lá bài số \(i\), chúng ta xóa vị trí đó khỏi bộ bài.

Lưu ý rằng \(n\), số lượng truy vấn, tối đa là 100. Chúng ta không cần phải gán lại nhãn cho tất cả các vị trí, chỉ cần thực hiện việc này cho \(n\) vị trí mà chúng ta quan tâm.

Giải pháp có thể được cài đặt theo hai cách, dựa trên góc nhìn nào bạn chọn ở đầu phần phân tích. Chương trình C++ ngắn gọn dưới đây dựa trên góc nhìn thứ hai, trong đó vị trí (pos) thay đổi như một con trỏ, và bộ bài không di chuyển, ngoại trừ việc chúng ta xóa một vị trí trong mỗi bước.

for (int j = 0; j < n; j++) answers[j] = -1;
for (int i = 1, pos = 0; i <= K; i++) {
  // Compute the next position, after wrap-around.
  pos = (pos + i - 1) % (K - i + 1);
  for (int j = 0; j < n; j++)
  if (answers[j] < 0) {
    if (queries[j] == pos+1) {
      queries[j] = -1; answers[j] = i;
    } else if (queries[j] > pos+1) {
      // The effect of deleting the next position.
      queries[j]--; 
    }
  }
}

Bạn có thể sử dụng một mẹo để kết hợp hai mảng queries[] và answers[] thành một. Chương trình chạy trong thời gian \(\Theta(n K)\).

Thông tin thêm:

Interval trees

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