Two frequency lists
War and Peace was cut in half, and for each half its words were written out from the most frequent to the rarest. Only the words that got into both lists were kept, so the lists consist of the same words, only in a different order. How similar are the two frequency dictionaries? One measure is how many words can be kept in both lists so that their order matches.
You are given two lists of the same n distinct words. Find the largest number of words that go in the same order in both lists, that is, the length of the longest common subsequence of the two lists.
Input
The first line holds n (1 ≤ n ≤ 100,000). The second holds the n distinct words of the first list, the third the same n words in the order of the second list, separated by spaces. A word is a non-empty string of letters and digits.
Output
One number: the largest number of words whose order in the two lists matches.
Examples
Example 1
6 и в не что он на и не в он что на
4
Example 2
4 князь пьер наташа андрей князь пьер наташа андрей
4
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 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 the longest common subsequence, but an n × n table with n = 100,000 is ten billion cells. How are these two lists simpler than two arbitrary strings?
2Hint 2
Each word occurs exactly once in each list. Replace each word of the first list with its number in the second. What is a common subsequence in the language of these numbers?
3The idea
Write out, for the words of the first list in order, their places in the second. A set of words goes in the same order in both lists exactly when in the first list they go from left to right and their places in the second increase. So the answer is the length of the longest increasing subsequence of these places, and the staircase finds it in O(n log n).
4Walkthrough
A dictionary “word → place in the second list” is built in one pass. Then go through the first list and put each word’s place on the staircase: a binary search for the first step no smaller, a replacement or a new step on top. The answer is the number of steps. The places are all different, so strictness is no trap here: bisect_left and bisect_right give the same.
On War and Peace: of the 403 words that got into the top five hundred of both halves of the novel, 72 go in the same order; of the 3210 words of the top five thousand, 338; of the 7442 words that occur at least twice in each half, 1259. For comparison, a random shuffle of a hundred thousand words keeps only 616 in the same order, about 2√n, as Ulam’s problem predicts. The frequency dictionaries of the two halves of the book are far more alike than random ones.
The same technique underlies the Hunt–Szymanski algorithm (1977) for the general case: if there are few pairs of equal elements in two sequences, the common subsequence is searched for over them, not over the whole table.
4+Solution
5Complexity
O(n log n) time and O(n) memory instead of the table’s O(n²).
6Common mistakes
- The common subsequence table. Correct but quadratic: on the test with a hundred thousand words it does not make it in time.
- Comparing the lists by position. The number of words standing at the same place in both lists is a different and much cruder measure: one extra shift at the start throws off every place after it.
Algorithms behind it
O(m · n)
2 problems
DP
Algorithm
Longest increasing subsequence
The longest rising chain of elements in their original order: patience and binary search in n log n.
O(n log n)
2 problems