Code Jam 2011 - Qualification Round: GoroSort

Lời giải

Bài toán này mang tính chất toán học rất cao, đòi hỏi nhiều suy nghĩ nhưng chỉ cần một ít mã nguồn để giải quyết chính xác.

Đối với một mảng \(A\) bất kỳ, gọi \(n(A)\) là số lượng phần tử chưa nằm đúng vị trí của nó. Kết quả mà chúng ta tìm kiếm đơn giản chính là \(n(A)\). Một khi bạn nhận ra điều này, việc tính toán chỉ là một vòng lặp đơn giản, nhưng làm thế nào để chứng minh nó?

Chứng minh

Trước tiên, hãy chỉ ra rằng số lần đấm kỳ vọng không bao giờ nhiều hơn \(n(A)\). Giả sử Goro luôn giữ chặt những phần tử đã ở đúng vị trí, và sau đó anh ta hoán vị ngẫu nhiên các phần tử còn lại. Gọi \(x(A)\) là số lần đấm kỳ vọng cần thiết để anh ta sắp xếp \(A\) bằng chiến lược này.

Bổ đề: \(x(A) = n(A)\) với mọi \(A\).

Chúng ta chứng minh điều này bằng quy nạp trên \(n(A)\). Nếu \(n(A) = 0\), mảng đã được sắp xếp, và ta hoàn thành. Để thiết lập quy nạp, giả sử chúng ta đã chứng minh bổ đề cho các giá trị nhỏ hơn của \(n(A)\) và bây giờ đang cố gắng chứng minh nó cho \(A\). Gọi \(p_t\) là xác suất để có đúng \(t\) phần tử vẫn sai vị trí sau lần đấm đầu tiên, và gọi \(x'_t\) là số lần đấm kỳ vọng cần thiết trong trường hợp đó. Chúng ta có ba quan sát:

1. \(p_0 \cdot 0 + p_1 \cdot 1 + p_2 \cdot 2 + \dots + p_N \cdot N = N - 1\). Nói cách khác, số lượng phần tử kỳ vọng vẫn sai vị trí sau lần đấm đầu tiên là đúng \(N - 1\), hay tương đương, số lượng phần tử kỳ vọng được đưa vào đúng vị trí sau lần đấm đầu tiên là đúng \(1\). Điều này suy ra từ "tính tuyến tính của kỳ vọng": Goro đang hoán vị \(N\) phần tử; mỗi phần tử có xác suất đúng \(1/N\) rơi vào vị trí chính xác, do đó, số lượng phần tử kỳ vọng rơi vào đúng vị trí là \(N \cdot 1/N = 1\).
2. \(x'_t = t\) với \(t \le N - 1\). Điều này đúng theo giả thiết quy nạp.
3. \(x'_N = x(A)\). Nếu không có phần tử nào được đưa vào đúng vị trí sau lần đấm đầu tiên, chúng ta sẽ lại hoán vị ngẫu nhiên tất cả chúng một lần nữa ở bước tiếp theo, vì vậy không có gì thay đổi, và do đó \(x'_N = x(A)\).

Bây giờ hãy viết công thức cho \(x(A)\):

Công thức này rút gọn thành \((N - x(A)) \cdot (1 - p_N) = 0\). Vì \(p_N < 1\), ta phải có \(x(A) = N\), và bổ đề được chứng minh.

Để hoàn tất chứng minh, chúng ta cần tính \(y(A)\), số lần đấm kỳ vọng cần thiết nếu Goro sử dụng chiến lược tối ưu (chưa biết). Vì \(y(A) \le x(A)\) theo định nghĩa, chúng ta đã chứng minh được \(y(A) \le n(A)\).

Để chứng minh ngược lại \(n(A) \le y(A)\), chúng ta có thể mở rộng chứng minh của bổ đề trước. Tuy nhiên có một vấn đề kỹ thuật: \(n(A)\) có thể tăng lên nếu Goro không giữ đủ các phần tử, do đó việc thiết lập quy nạp trên \(n(A)\) là phức tạp. Chúng ta sẽ giải quyết điều này bằng một chứng minh riêng biệt, sử dụng giả thiết quy nạp hơi khác một chút.

Bổ đề 2: Gọi \(K\) là một số nguyên không âm. Khi đó với bất kỳ \(k \le K\), mệnh đề \(y(A) = k\) tương đương với mệnh đề \(n(A) = k\).

Chứng minh bằng quy nạp trên \(K\). Cả \(y(A) = 0\) và \(n(A) = 0\) đều tương đương với việc mảng đã được sắp xếp, vì vậy trường hợp \(K = 0\) là hiển nhiên. Giả sử đã chứng minh bổ đề cho \(K\), và đang cố gắng chứng minh cho \(K+1\). Chọn \(A\) sao cho \(y(A)\) là giá trị nhỏ nhất có thể lớn hơn \(K\) và xem xét chiến lược tối ưu của Goro. Gọi \(T\) là số lượng các phần tử hoặc là (a) không ở đúng vị trí trong \(A\), hoặc (b) được hoán vị khi Goro đấm bàn. Định nghĩa \(p_i\) và \(x'_i\) như trước. Lưu ý rằng \(T \ge n(A) \ge K+1\) theo giả thiết quy nạp.

Tương tự bổ đề trước, ta có thể chứng minh:

• \(p_0 \cdot 0 + p_1 \cdot 1 + p_2 \cdot 2 + \dots + p_T \cdot T \ge T - 1\).
• \(x'_i = i\) với \(i \le K\). Điều này suy ra trực tiếp từ giả thiết quy nạp.
• \(x'_i \ge y(A)\) với \(i > K\). Theo giả thiết quy nạp, \(n(A') > K\) dẫn đến \(y(A') > K\), từ đó suy ra \(y(A') \ge y(A)\).

Viết \(y(A)\) tương tự:

Rút gọn thành \((y(A) - T) \cdot (1 - p_{K+1} - \dots - p_T) \ge 0\). Cụm thứ hai phải dương, vì vậy ta phải có \(y(A) \ge T \ge n(A) \ge K+1\). Dấu bằng xảy ra khi và chỉ khi \(n(A) = K+1\). Bổ đề đầu tiên đảm bảo \(y(A) \le x(A) \le K+1\) trong trường hợp này, và chứng minh hoàn tất!

Cách cài đặt và Độ phức tạp

• Cách cài đặt: Duyệt qua mảng, đếm số lượng phần tử \(A[i]\) sao cho \(A[i] \neq i+1\) (giả sử mảng là hoán vị của các số từ \(1\) đến \(N\)).
• Độ phức tạp: \(O(N)\) cho mỗi bộ test.

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