Jaewoo Song

### Categories

• Tech

https://www.acmicpc.net/problem/14465

I solved this in $O(N^2)$ with one bigger for loop and partial second for loop.

But there is a solution with $O(N)$ time complexity, which uses partial sum.

I have thought that I don’t have to use this since I was a high school student, but as well as the last SCPC preliminary problem, partial sum substantially reduces the time complexity.

If we assume that the number of malfunctioning traffic lights from $1$ to $i$ is partialSums[i], the number of broken lights from $i$ to $i+K-1$ is partialSums[i+K-1] - partialSums[i].

If we initializes partialSums array properly, this is easy approach.

#include <iostream>
#include <vector>

using namespace std;

int N, K, B;
vector<int> partialSums;

int main() {

scanf("%d %d %d", &N, &K, &B);

partialSums.assign(N+1, 0);

for (int i=1; i<=B; ++i) {
int input;
scanf("%d", &input);
partialSums[input] = 1;
}

for (int i=0; i<N; ++i) {
partialSums[i+1] += partialSums[i];
}

int count = N;

for (int i=1; i<=N-K+1; ++i) {
if (partialSums[i+K-1] - partialSums[i] <= count) {
count = partialSums[i+K-1] - partialSums[i];
}
}

printf("%d\n", count);

return 0;
}


In addition, the process to get partial sums was interesting, which first makes the index of broken light $1$ and adds them sequentially.

I think I learned about it as I was in high school, but maybe I have forgotten it.