Official Analysis (Java)

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)$

Copy
from typing import NamedTuple


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


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