Phân tích

Test Set 1

Giới hạn đủ nhỏ để thử mọi cặp trong \(K^2\) cặp số có thể mua. Với mỗi cặp, ta tính xác suất thắng cho từng giá trị rút thăm; có \(K\) khả năng của \(c\). Nếu với mỗi \(c\) ta kiểm tra khoảng cách đến từng \(P_i\) và hai lựa chọn của mình, tổng thời gian là \(O(K^3N)\), đủ nhanh.

Có nhiều tối ưu. Một cách đơn giản là dùng cấu trúc có thứ tự để tìm “số đã chọn gần nhất”, giảm bước đó xuống \(O(\log N)\) và tổng thời gian xuống \(O(K^2N\log N)\). Cũng có thể tính khoảng cách từ mỗi \(c\) đến các \(P_i\) đúng một lần, độc lập với lựa chọn của ta, giảm tiếp xuống \(O(K^2)\).

Test Set 2

Ta có thể tối ưu mọi giai đoạn của lời giải trên. Nếu mỗi số đã xuất hiện trên ít nhất một vé, đáp án luôn là \(0\) như ví dụ. Nếu không, chia các số chưa được mua trong \(\{1,2,\ldots,K\}\) thành các đoạn nằm giữa những giá trị \(P_i\). Ví dụ, nếu \(P_i\) là \(3,4,8,3\) và \(K=8\), các đoạn là \([1,2]\) và \([5,7]\).

Nếu chỉ đặt một vé của ta trong một đoạn:

• Nếu đoạn chứa \(1\) hoặc \(K\), ta có thể gần nhất với toàn bộ đoạn bằng cách chọn sát giá trị \(P_i\) duy nhất chặn đoạn; trong ví dụ, chọn \(2\) ở đoạn \([1,2]\).
• Nếu đoạn được bao bởi hai giá trị \(P_i\), ta có thể gần nhất với nhiều nhất một nửa số nguyên của đoạn, làm tròn lên; đạt được bằng cách chọn một đầu đoạn, như chọn \(5\) hoặc \(7\) trong \([5,7]\).

Nếu đặt cả hai vé trong cùng một đoạn, ta có thể gần nhất với mọi số trong đoạn bằng cách chọn cả hai đầu, chẳng hạn \(5\) và \(7\) ở \([5,7]\).

Điều đó cho thấy ta chỉ cần xét những số nằm sát một số đã mua. Ta có thể quay lại lời giải Test Set 1 cuối cùng, nhưng giới hạn hai lựa chọn vào những số sát một \(P_i\); khi đó các thừa số \(K\) trong độ phức tạp được thay bằng \(O(N)\), đủ nhanh với cài đặt thích hợp.

Thêm vài bước suy luận cho lời giải hiệu quả hơn nhiều. Chỉ có \(O(N)\) cách đặt cả hai vé trong cùng một đoạn, nên có thể kiểm tra từng cách. Nếu chọn hai đoạn khác nhau, luôn tối ưu khi chọn hai đoạn có giá trị một-vé lớn nhất; không cần thử từng cặp. Ta chỉ cần thêm một trường hợp, tính trong \(O(N)\) để tìm hai giá trị lớn nhất.

Tổng cộng, sau khi sắp xếp mảng để tìm các đoạn, thuật toán chạy tuyến tính. Cần cẩn thận với các trường hợp biên: không còn số nào hoặc chỉ còn một số trong \([1,K]\) chưa xuất hiện trong các \(P_i\), và danh sách đoạn chỉ có một đoạn.

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng 1C, bài Closest Pick.