Tutorial — Optimal Arsenal Calibration

Bài toán yêu cầu tối thiểu hóa số súng cần thay đổi, tương đương với việc tìm một khoảng hỏa lực $[L, L + k]$ chứa được nhiều giá trị hỏa lực ban đầu $p_i$ nhất. Nhận thấy rằng với các khẩu súng có $f_i \le k$, ta luôn luôn chọn được sát thương $d_i$ mới để $p_i$ rơi vào khoảng này mà không tạo ra bất kỳ ràng buộc nào lên $L$.

Các khẩu súng có $f_i > k$ chỉ có thể đạt được hỏa lực trong khoảng $[L, L + k]$ nếu khoảng này chứa một bội số của $f_i$. Nếu giả sử khẩu súng thứ $j$ được giữ nguyên hỏa lực $p_j$, ta có thể đặt $L = p_j - x$ với $0 \le x \le \min(k, p_j - 1)$, từ đó biến đổi điều kiện của mỗi khẩu súng thành một tập hợp các đoạn giá trị khả thi của $x$.

Sử dụng mảng hiệu kích thước $O(k)$ để cộng dồn các đoạn giá trị của $x$ thỏa mãn cho từng súng có $f_i > k$ cũng như đếm số súng giữ nguyên được hỏa lực ban đầu. Duyệt qua $x$ từ $0$ đến $\min(k, p_j - 1)$ để kiểm tra điều kiện hợp lệ và cập nhật số lượng súng giữ nguyên lớn nhất.