USACO Bronze 2022 Open - Counting Liars

Authors: Chongtian Ma, Juheon Rhee

Edit This Page

Table of Contents

ExplanationImplementation

Official Analysis (Java)

Explanation

After we sort the input, an important observation is that if Bessie is at position xx, then the number of cows lying are all the cows with position less than xx that says "L" plus all the cows with a position greater than xx 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: O(Nlog⁡N)\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!

Join Forum