Phân tích: Magical, Marvelous Tour

Có một dãy các thiết bị, mỗi thiết bị chứa một số lượng bóng bán dẫn đã biết, và trong số đó có 1 chiếc bóng bán dẫn vàng mà cả hai người chơi đều muốn. Người chơi 1 (Arnar) chọn một đoạn của dãy (điều này sẽ chia dãy thành 3 phần \([0, i-1]\), \([i, j]\), \([j+1, N-1]\)), sau đó người chơi 2 (Solveig) sẽ chọn một trong ba phần đó để lấy, để lại hai phần còn lại cho người chơi 1. Bài toán yêu cầu chúng ta tìm xác suất Arnar nhận được bóng bán dẫn đặc biệt, giả định cả hai người chơi đều hành động tối ưu và mọi bóng bán dẫn đều có xác suất trở thành bóng bán dẫn vàng như nhau.

Đầu tiên, chúng ta nhận thấy rằng có thể tính tổng của bất kỳ đoạn nào trong dãy trong thời gian \(O(1)\) sau khi tiền xử lý mảng cộng dồn (prefix sum). Mảng cộng dồn có thể được xây dựng bằng công thức sau từ \(0\) đến \(N\):

Sau đó, đối với bất kỳ cách phân chia dãy thiết bị nào, chúng ta có thể tìm số lượng bóng bán dẫn bên trong mỗi phần một cách hiệu quả bằng cách sử dụng:

Để xác định các ranh giới tốt nhất mà Arnar có thể đặt, chúng ta có thể duyệt qua tất cả các ranh giới có thể và lưu lại ranh giới tốt nhất. Trong code, điều này tương ứng với việc sử dụng 2 vòng lặp for bao phủ tất cả các tổ hợp của \(i\) và \(j\) với \(i \le j\). Với mỗi cặp, chúng ta có được số lượng bóng bán dẫn trong mỗi phần kết quả. Vì Solveig sẽ luôn lấy phần có nhiều bóng bán dẫn nhất, điểm số của Arnar cho một lựa chọn ranh giới cụ thể là tổng số bóng bán dẫn trừ đi giá trị lớn nhất của một trong ba phần. Nói cách khác, nếu ba phần có tổng lần lượt là \(S_1, S_2, S_3\), Solveig sẽ lấy \(\max(S_1, S_2, S_3)\), và Arnar sẽ nhận được tổng các phần còn lại. Xác suất của Arnar là \(((\sum \text{tất cả}) - \max(S_1, S_2, S_3)) / (\sum \text{tất cả})\).

Giải pháp này chạy trong \(O(N^2)\) vì chúng ta xem xét tất cả các tổ hợp của \(i\) và \(j\). Điều này đủ tốt để vượt qua Small dataset; tuy nhiên, nó sẽ bị quá thời gian khi chạy Large dataset. Để vượt qua Large dataset, chúng ta nên tìm một thuật toán \(O(N \log N)\) hoặc \(O(N)\).

Thuật toán \(O(N \log N)\)

Quan sát quan trọng đầu tiên: chúng ta có thể diễn đạt lại bài toán này là tìm cách phân chia 3 phần sao cho giá trị lớn nhất của bất kỳ phần nào là nhỏ nhất, vì Solveig chắc chắn sẽ chọn phần có nhiều bóng bán dẫn nhất.

Thứ hai, Arnar nên chọn các ranh giới sao cho giá trị của 3 phần càng gần nhau càng tốt (nếu không Solveig sẽ chiếm ưu thế bằng cách chọn phần có nhiều bóng bán dẫn hơn đáng kể so với 2 phần còn lại).

Vì mảng cộng dồn tăng dần, chúng ta có thể sử dụng tìm kiếm nhị phân. Ý tưởng thuật toán là duyệt qua các giá trị có thể có của \(i\) (ranh giới bên trái), sau đó tìm kiếm nhị phân cho \(j\) (ranh giới bên phải) tối ưu ứng với \(i\) đó. Cụ thể, chúng ta muốn giá trị \(j\) sao cho giá trị của phần giữa \([i, j]\) và phần bên phải \([j+1, N-1]\) gần nhau nhất.

Ta mô tả cụ thể quá trình tìm kiếm nhị phân. Bắt đầu với hai con trỏ biểu diễn toàn bộ khoảng có thể của ranh giới phải. Điểm giữa hai con trỏ là pivot — dự đoán hiện tại cho ranh giới phải. Nếu phần bên phải pivot lớn hơn phần bên trái pivot, ranh giới tốt hơn nằm về bên phải; trong trường hợp ngược lại, nó nằm về bên trái. Vì vậy, sau mỗi bước ta loại được một nửa khoảng, cho đến khi chỉ còn một khả năng.

Hãy xét ví dụ lấy từ dữ liệu mẫu thứ hai:

INPUT: 10 17 1 7 1  generates  [2 5 1 4 7 3 6 2 5 1]

Giả sử ranh giới trái nằm giữa chỉ số \(0\) và \(1\), và ta đang tìm ranh giới phải tốt nhất. Dự đoán đầu tiên đặt ranh giới phải ở giữa ranh giới trái và cuối mảng — trong ví dụ là giữa các giá trị \(3\) và \(6\). Hình dưới trình bày từng vòng của tìm kiếm nhị phân. Cột đầu minh họa mảng và hai ranh giới đang xét; ba cột kế là giá trị ba phần; hai cột cuối là số bóng bán dẫn mỗi người chơi nhận được.

Lưu ý ranh giới phải luôn dịch theo hướng làm tăng phần đang thiếu giữa phần giữa và phần phải. Chẳng hạn, ở hàng thứ hai của hình, ta dịch sang trái vì tại hàng đầu giá trị phần giữa lớn hơn giá trị phần phải.

Vì chúng ta tìm được cách phân chia tối ưu cho mỗi \(i\), kết quả cuối cùng là kết quả tốt nhất trong số đó. Tìm kiếm nhị phân mất \(O(\log N)\) và chúng ta thực hiện điều đó cho \(N\) ranh giới trái, tổng thời gian chạy là \(O(N \log N)\).

Thuật toán \(O(N)\)

Chúng ta có thể làm tốt hơn nữa. Ví dụ, chúng ta có thể tìm một cận dưới chặt chẽ cho điểm số của Solveig bằng cách trả lời câu hỏi: "Arnar có thể tạo ra một cách phân chia 3 phần sao cho Solveig nhận được tối đa \(Z\) bóng bán dẫn không?". Rõ ràng có một giá trị \(K\) sao cho câu trả lời là "không" với \(Z < K\) và "có" với \(Z \ge K\), nghĩa là \(K\) có thể được tìm thấy bằng tìm kiếm nhị phân trên giá trị \(Z\).

Để trả lời câu hỏi đó với một giá trị \(Z\) cho trước, Arnar có thể chọn phần bên trái và phần giữa một cách tham lam: chọn \(i\) lớn nhất có thể sao cho phần bên trái không quá \(Z\) bóng bán dẫn, sau đó chọn \(j\) lớn nhất có thể sao cho phần giữa không quá \(Z\). Nếu phần bên phải còn lại cũng không quá \(Z\), câu trả lời là "có". Các vị trí \(i, j\) này có thể được tìm nhanh chóng bằng tìm kiếm nhị phân trên mảng cộng dồn trong \(O(\log N)\).

Chiến thuật này cần \(O((\log N)^2)\) cho tìm kiếm nhị phân ngoài: ta đặt \(O(\log N)\) câu hỏi, mỗi câu được trả lời trong \(O(\log N)\). Dĩ nhiên, nó còn cần mảng tổng tiền tố, mất \(O(N)\) để xây dựng. Vì vậy, độ phức tạp tổng thể là \(O(N)\).

Có lẽ hơi bất ngờ, bài toán thậm chí có thể được giải trong \(O((\log r)(\log N)^2)\)! Hãy thử tìm cách dùng một ít toán học phức tạp để tránh tính đủ \(O(N)\) phần tử của mảng tổng. Gợi ý: cần khai thác công thức đặc biệt xác định số bóng bán dẫn trong mỗi thiết bị.

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