Using partial sums

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.

Categories