USACO Silver 2016 December - Cities & States

Java

C++

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

Time Complexity: $\mathcal{O}(N\log N)$ with map, $\mathcal{O}(N)$ with unordered_map.

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

A faster solution is to convert each string into an integer in the range $[0,26^4)$ and use an array instead of a map.

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

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;