Quy hoạch động theo ngân sách

Gọi độ dài chuỗi đầu vào là \(N\). Có \(N+1\) “khe” mà phần tử mới có thể rơi vào, đánh số từ 0 đến \(N\): khe 0 nằm trước phần tử đầu tiên, khe \(N\) nằm sau phần tử cuối cùng.

Tại mọi thời điểm tìm kiếm, ta đã thu hẹp vị trí đúng thành một khoảng các khe khả dĩ. Việc xác định khe đúng trong khoảng ấy được gọi là “giải” khoảng.

Với chi phí \(C\) và vị trí \(X\), gọi \(f(C,X)\) là khe ngoài cùng bên phải của khoảng lớn nhất bắt đầu tại \(X\) mà ta có thể giải với chi phí không quá \(C\). Ta tính \(f\) bằng quy hoạch động. Rõ ràng, nếu \(C=0\) thì \(f(C,X)=X\) và khoảng rỗng, vì mọi phép so sánh đều tốn ít nhất 1.

Giả sử \(X<Y\) và ta có thể giải khoảng \([X,Y]\) với chi phí không quá \(C\). Phép so sánh đầu tiên phải ở một chỉ số \(i\in[X,Y-1]\), với chi phí \(a_i\). Sau đó khe đúng nằm ở khoảng bên trái \([X,i]\) hoặc khoảng bên phải \([i+1,Y]\). Cả hai phải giải được trong chi phí không quá \(C-a_i\), tức

Ta cần \(Y\) lớn nhất thỏa các điều kiện này. Với một lựa chọn \(X,i\), luôn lấy \(Y=f(C-a_i,i+1)\), vì theo định nghĩa đó là \(Y\) lớn nhất. Thay vì thử mọi \(i\) trong \([X,f(C-a_i,X)]\), ta duyệt từng giá trị có thể của \(a_i\) từ 1 đến 9 và chỉ thử chỉ số \(i\) lớn nhất trong khoảng ấy có giá trị đó. Một chỉ số nhỏ hơn với cùng \(a_i\) không thể tạo ra \(Y\) lớn hơn. Nếu không có \(i\) dùng được vì \(C\) quá nhỏ hoặc \(X=N\), thì \(f(C,X)=X\).

Tính \(f(C,X)\) theo \(C\) tăng dần cho tới khi gặp \(C\) nhỏ nhất sao cho \(f(C,0)=N\). Đây chính là đáp án.

Độ phức tạp

Giá trị \(C\) lớn nhất xảy ra khi mọi chi phí đều bằng 9; khi đó không thể làm tốt hơn tìm kiếm nhị phân chuẩn, cần \(O(\log N)\) phép so sánh, mỗi phép tốn 9. Vì vậy miền trạng thái có kích thước \(9\log N\times N\). Mỗi trạng thái thử 9 giá trị, là thời gian \(O(N\log N)\) với hằng số tương đối lớn do hai thừa số 9 vừa nêu.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2015 - World Finals - Costly Binary Search, kho Google Coding Competitions (Apache-2.0).