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(N)\mathcal{O}(N)

C++

The time complexity of the below solution is actually O(Nlog⁡N)\mathcal{O}(N\log N), since it uses map. Using unordered_map or vector would bring the complexity back down to O(N)\mathcal{O}(N).

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


int main() {
	ifstream read("citystate.in");
	int N;
	read >> N;


	vector<pair<string, string>> pairs;
	for (int i = 0; i < N; i++) {

Java

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


public class CityState {
	static class Pair {
		public String city;
		public String state;
		public Pair(String city, String state) {
			this.city = city;
			this.state = state;

Python

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)

C++

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


int index(string s) {
	int ind = 0;
	for (char &c : s) { ind = 26 * ind + (c - 'A'); }
	return ind;
}


int main() {

Java

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


public class CityState {
	static class Pair {
		public String city;
		public String state;
		public Pair(String city, String state) {
			this.city = city;
			this.state = state;

Python

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