We start by making an observation about the optimal block of signals to consider such that we minimize the number of signals that need to be repaired. We claim that there is an optimal block where the leftmost signal in the block does not need to be repaired. Assume for the sake of contradiction that this is not the case, and consider any optimal block of signals. If we slide it over to the leftmost contiguous block to the right of the optimal one such that the leftmost block does not need to be repaired, note that we removed signals that did need to be repaired. Therefore, in the worst case, this block requires at most the original number of blocks to be repaired, making it optimal.

Therefore, we only need to constrain ourselves to consider contiguous blocks where the leftmost block does not need to be repaired. If we sort the signals that are working, we can use binary search to find the rightmost working signal that would be within a block of $K$. This gives us an $O(N \log N + B \log N)$ algorithm.

Here is Mark Gordon's code, which is actually $O(N \log N + B)$. His solution leverages the fact that as we iterate over the leftmost signal from left to right, the rightmost signal that would be valid also iterates from left to right.

#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> A; int main() { int N, K, B; cin >> N >> K >> B; A.resize(B); for (int i = 0; i < B; i++) { cin >> A[i]; } sort(A.begin(), A.end()); int hia = 0; while (hia < B && A[hia] <= K) { hia++; } int result = hia; for (int i = 0; i < B; i++) { if (A[i] + K > N) { break; } while (hia < B && A[hia] <= A[i] + K) { hia++; } result = min(result, hia - i - 1); } cout << result << endl; return 0; }