USACO Silver 2017 February - Why Did the Cow Cross the Road II

Authors: Albert Zhu, Juheon Rhee, Sachet Abeysinghe

Appears In

Silver - Introduction to Prefix Sums

Explanation

We can represent this problem as an array $a$ of $N$ signals, such that the $i$ -th signal is $0$ if it is working and $1$ if it is not working. Now we need to find a subarray of length $K$ with the least number of $1$ s (i.e., the least sum).

We can use prefix sums to find the number of $1$ s (broken signals) across all subarrays of length $K$ and then take the minimum.

Implementation

Time Complexity: $\mathcal{O}(N)$

C++

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {

Java

import java.io.*;
import java.util.*;

public class MaxCross {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("maxcross.in"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

Python

with open("maxcross.in") as read:
	n, k, b = [int(i) for i in read.readline().split()]

	signals = [0 for _ in range(n)]
	for _ in range(b):
		signals[int(read.readline()) - 1] += 1

# prefix sums precomputation
pref_sum = [0]
for i in range(n):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!