USACO Silver 2016 December - Cities & States

Authors: Benjamin Qi, Kevin Sheng

Edit This Page

Official Editorial (Java)

As the editorial mentions, we can store the number of times a given four-letter string appears in a map.

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