Town codes
Each town needs its own code of three capital Latin letters, like airports have. The rule is this: the first letter of the code is the first letter of the name, and the other two are letters of the name that come later in it, in the same order. For BERN the codes BER, BEN and BRN fit, for BRNO BRN, BRO and BNO. Two towns cannot be given the same code, even if their names are the same. What is the largest number of towns that can be given codes?
Tests 4–6 are real towns of the world with at least 10,000 inhabitants from GeoNames: all 45,204, the twenty thousand largest, and all whose names begin with S. Spaces, hyphens, apostrophes and diacritics are removed from the names, letters such as Ł or Ø are replaced with L and O, and names shorter than three letters are left out.
Input
The first line holds the number of towns n (1 ≤ n ≤ 50,000). Then n lines, names of capital Latin letters, from 3 to 40 letters each. There are at most 1.2 · 10⁶ distinct pairs “name, fitting code”.
Output
One number: the largest number of towns that get codes.
Examples
Example 1
4 BERN BRNO BREST BARI
4
Example 2
4 ORAN ORA ORN OAN
3
Limits
- Time · Python
- 9000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
This is a pairing problem: towns on the left, codes on the right, an edge means “the code fits the town”. A maximum matching is needed. How many codes could be needed in all, and how many edges does the graph have on all the towns of the world?
2Hint 2
There are 45 thousand towns, and 16,046 codes fit anyone at all: two thirds of the towns will be left without a code. Why is this bad for an algorithm that looks for a partner for each town in turn?
3The idea
A matching is a flow in the network source → towns → codes → sink with all capacities 1. Each town has one incoming arc and each code one outgoing arc, so the network is a unit network, and by the theorem on unit networks Dinic's algorithm makes at most 2√V + 1 phases, each in O(E). It is handy to write it as the Hopcroft–Karp algorithm: a phase lays the towns out by the length of the alternating path from a free town, and depth-first search with pointers takes as many vertex-disjoint shortest paths as fit.
4Walkthrough
For each name go through the pairs of positions i < j after the first letter and collect the set of codes without repeats. Then the phases. The breadth-first search starts from all free towns at once: from a town go along each of its codes, and if the code is taken, the next layer is the town holding it. As soon as a free code is met, the shortest length is known. Then from each free town a depth-first search goes along the layers only; the pointer nxt[u] remembers which code of town u to try next, and a town whose codes have run out is marked a dead end until the end of the phase. A path found is flipped: each town on it takes the code through which the search came.
On all the towns of the world there are five phases. In Go it is handy to treat codes as numbers 676 · first + 26 · second + third; then an array of 17,576 elements replaces a dictionary.
4+Solution
5Complexity
There are as many edges as “name, code” pairs: about a million on all the towns of the world. Each phase is O(E), there are O(√V) phases, five in fact. The Python reference fits in a little over a second.
6Common mistakes
- One path per search. A breadth-first search looks for one augmenting path, the path is flipped, the search starts again: this is how Edmonds–Karp works. This is
wrong.py: each code handed out costs a search of the whole graph, and almost fifteen thousand codes must be handed out. On all the towns it does not finish in time. - Kuhn. Depth-first search from each town in turn is also correct, but a town that does not get a code goes through everything the alternating paths reach before giving up, and there are thirty thousand such towns. On all the towns of the world Kuhn's algorithm in Python runs for almost a minute.
- Greedily. If each town is given its first free code, on all the towns 14,049 get codes instead of 14,864: an early town can take a later town's only code.
- Repeats. In a name like SANTAANA the same triple of letters comes from different positions. It is one edge, and if repeats are not removed, the graph swells.
Algorithms behind it
O(V² E)
2 problems
GRA
Algorithm
Bipartite matching
The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall.
O(E √V)
2 problems