USACO Bronze 2022 Open - Counting Liars

Authors: Chongtian Ma, Juheon Rhee

Appears In

Bronze - Basic Complete Search

Explanation

After we sort the input, an important observation is that if Bessie is at position $x$ , then the number of cows lying are all the cows with position less than $x$ that says "L" plus all the cows with a position greater than $x$ that says "G".

Given this, we can loop through every cow's position and compute the total number of liars by using a forwards loop and a backwards loop.

The answer is the minimum liars over all the positions we looped over.

Implementation

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

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;

	vector<pair<int, char>> cows(n);
	for (int i = 0; i < n; i++) {
		// The position is read into .first for sorting.

Java

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

public class CountingLiars {
 	Code Snippet: Cow Class (Click to expand)

	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(read.readLine());

Python

from typing import NamedTuple


class Cow(NamedTuple):
	pos: int
	statement: str


n = int(input())
cows = []

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!