Table of Contents

ExplanationImplementation

Official Editorial (Java)

Explanation

Let's represent each given pair as a 4-letter string (city prefix + state code) and use a map to track frequencies. For each string we check if its mirror exists and increase our count accordingly.

Implementation

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

from collections import defaultdict




pairs = []
with open("citystate.in") as read:
	for _ in range(int(read.readline())):
		city, state = read.readline().strip().split()
		city = city[:2]  # We only care about the first two letters of the city
		pairs.append((city, state))

However, note that we can optimize this by converting each string into an integer and using an array instead of a map.

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

def index(s: str) -> int:
	ind = 0
	for c in s:
		ind = 26 * ind + (ord(c) - ord("A"))
	return ind




pairs = []
with open("citystate.in") as read:
	for _ in range(int(read.readline())):

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