Phân tích: Saving the Universe

Bài toán đầu tiên trong Google Code Jam mới, không ngạc nhiên, là về các công cụ tìm kiếm, và cũng là kỳ tích vĩ đại trong việc cứu vũ trụ một cách tiết kiệm nhất. Tuy nhiên, bỏ qua những điều hoa mỹ, bản thân bài toán này khá dễ.

Liệt kê tất cả các truy vấn từng cái một và chia chúng thành các đoạn. Mỗi đoạn sẽ là một khoảng thời gian mà chúng ta sử dụng một công cụ tìm kiếm duy nhất, và khi chúng ta chuyển từ đoạn này sang đoạn khác, chúng ta sẽ thay đổi công cụ tìm kiếm đang dùng. Bạn có thể nói gì về mỗi đoạn? Chà, một điều chắc chắn là:

Tuyệt đối không để tên của cả \(S\) công cụ tìm kiếm khác nhau cùng xuất hiện dưới dạng truy vấn trong một đoạn. (*)

Tại sao lại như vậy? Bởi vì nếu tất cả \(S\) cái tên đều xuất hiện trong một đoạn, thì bất kỳ công cụ tìm kiếm nào được sử dụng cho đoạn đó cũng sẽ gặp ít nhất một truy vấn trùng với tên của nó, do đó làm vũ trụ nổ tung!

Làm việc theo hướng ngược lại, (*) là tất cả những gì chúng ta cần đạt được; miễn là bạn có thể phân chia danh sách các truy vấn thành các đoạn như vậy, nó sẽ tương ứng với một kế hoạch cứu vũ trụ. Bạn thậm chí không cần quan tâm đến việc công cụ nào được sử dụng cho một đoạn; bất kỳ công cụ nào không xuất hiện dưới dạng truy vấn trong đoạn đó đều được. Tuy nhiên, đôi khi bạn có thể chọn cùng một công cụ cho hai đoạn liên tiếp, và tự cười nhạo mình khi nhận ra điều đó; tại sao mình không gộp hai đoạn đó thành một? Vì nhiệm vụ của bạn là sử dụng càng ít đoạn càng tốt, rõ ràng là bạn muốn làm cho mỗi đoạn dài nhất có thể.

Điều này dẫn đến giải pháp tham lam: Bắt đầu từ truy vấn đầu tiên, thêm từng truy vấn một vào đoạn hiện tại cho đến khi tên của tất cả \(S\) công cụ tìm kiếm đều đã xuất hiện. Sau đó, chúng ta tiếp tục quá trình này trong một đoạn mới cho đến khi tất cả các truy vấn được xử lý.

Mã mẫu bằng C++, trong đó st là tập hợp các truy vấn trong đoạn hiện tại, q là truy vấn tiếp theo và count là số lần chuyển đổi.

st.clear();
count = 0;
for (int i=0; i<Q; i++) {
  getline(cin, q);
  if (st.find(q) == st.end()) {
    if (st.size() == S-1) {
      st.clear();
      count++;
    }
    st.insert(q);
  }
}

Nếu st là một hashset (tập hợp băm), bạn có thể kỳ vọng giải pháp chạy trong thời gian \(O(Q)\). Lưu ý rằng giải pháp này sử dụng thực tế là mỗi truy vấn sẽ là một tên công cụ tìm kiếm, vì vậy chúng ta có thể bỏ qua danh sách các tên được cung cấp trong đầu vào (chỉ cần biết số lượng \(S\)).

Chứng minh tính đúng đắn

Hãy chứng minh rằng cách tiếp cận tham lam luôn đưa ra câu trả lời tối ưu. Hãy coi quy trình này gồm \(Q\) bước và chúng ta muốn chỉ ra rằng, với mỗi \(i\), có (ít nhất) một lựa chọn tối ưu khớp với chúng ta trong \(i\) bước đầu tiên. Chúng ta thực hiện việc này bằng phương pháp quy nạp cho \(i = 0\), sau đó \(i = 1\), v.v. Mệnh đề cho \(i = Q\) khi được chứng minh là đúng sẽ ngụ ý rằng thuật toán của chúng ta là chính xác.

Vì vậy, các điểm chính trong bước quy nạp \(i\):

1. Nếu việc thêm truy vấn tiếp theo sẽ làm vũ trụ nổ tung (tức là truy vấn này khiến cho tất cả \(S\) công cụ tìm kiếm đều đã xuất hiện trong đoạn hiện tại), chúng ta phải bắt đầu một đoạn mới. Bất kỳ lựa chọn tối ưu nào khớp với chúng ta trong \((i-1)\) bước trước đó cũng phải làm như vậy.
2. Nếu việc thêm truy vấn tiếp theo không làm vũ trụ nổ tung, chúng ta không bắt đầu một đoạn mới. Chúng ta biết có một giải pháp tối ưu \(R\) khớp với chúng ta trong \((i-1)\) bước. Ngay cả khi trong \(R\) một đoạn mới được bắt đầu ở bước \(i\), chúng ta có thể sửa đổi nó một chút. Gọi \(R'\) là kế hoạch khớp với \(R\), nhưng thay vì bắt đầu một đoạn mới ở bước thứ \(i\), chúng ta trì hoãn việc này đến bước thứ \((i+1)\). Rõ ràng là \(R'\) cũng sẽ giữ cho vũ trụ an toàn và không có nhiều lần chuyển đổi hơn \(R\). Vì vậy, \(R'\) cũng là một giải pháp tối ưu và khớp với lựa chọn của chúng ta trong \(i\) bước đầu tiên.

Các lập luận tương tự cũng có tác dụng với nhiều thuật toán tham lam khác, bao gồm cả thuật toán cây khung nhỏ nhất (MST) được yêu thích.

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