The vocabulary of two volumes
A linguist compares the language of the first and last volumes of War and Peace. They wrote out the words that occur in both volumes and ordered them twice: by frequency in the first volume and by frequency in the fourth (with equal frequency, alphabetically). If the language had not changed, the lists would coincide. As the measure of divergence the linguist chose the number of pairs of words that stand in different order in the two lists: in the first list word u is above word v, and in the second below it. Help count them.
Two tests are real frequency lists of the novel, in the original Russian: the first volume against the fourth and the first against the second.
Input
The first line holds n (1 ≤ n ≤ 200,000), the number of words. The second line holds n distinct words in the order of the first list, the third the same words in the order of the second. Words consist of lowercase Russian or Latin letters, up to 20 letters long.
Output
One number: how many pairs of words have different order in the two lists.
Examples
Example 1
4 мир война князь пьер война мир пьер князь
2
Example 2
5 a b c d e e d c b a
10
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 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
Number the words by the first list: the first word is 0, the second 1 and so on. Rewrite the second list with these numbers. What does “a pair in different order” mean for the resulting sequence of numbers?
2Hint 2
3Hint 3
During a merge an element is taken from the right half. With which elements of the left half does it form an inversion, and how many of them are left?
4The idea
After renumbering, the answer is the number of inversions in the sequence of numbers of the second list. Each inversion is a pair with both elements in the left half, both in the right, or one on the left and the other on the right. The recursion counts the first two kinds, and the merge itself the third. When element right[j] leaves the right half, it is smaller than all elements of the left half not yet taken (otherwise they would have been taken), and in the original sequence it stood to the right of each of them. So it forms an inversion with exactly len(left) − i elements, and each pair “across the middle” is counted exactly once, at the moment the smaller of the two goes into the result.
5Walkthrough
A dictionary “word → place in the first list” is built in one pass. Then an ordinary merge sort with one added counter: on every take from the right, add the number of elements left on the left. The sort orders the sequence as well, but we do not need its result, only the counter.
The answer on real data: of 3145 words frequent in both volumes, 1,295,773 pairs are ordered differently, about a quarter of almost five million. In statistics this quantity is converted into Kendall’s rank correlation coefficient: τ = 1 − 4D / (n(n − 1)), where D is the number of discordant pairs. For the first and fourth volumes τ ≈ 0.48: the vocabularies are noticeably alike but far from identical.
5+Solution
6Complexity
Renumbering is O(n) with a dictionary, merge sort with a counter O(n log n): for 200,000 words, about three and a half million comparisons instead of twenty billion for trying pairs.
7Common mistakes
- Trying pairs. Correct, but quadratic on the large tests and over the time limit.
- A 32-bit counter. The answer reaches n(n − 1)/2 ≈ 2·10¹⁰: in the fifth test the second list is the first reversed. In Python and Go (where
intis 64-bit) this is no worry; in C++ or Java you needlong longorlong. - Alphabetical inversions. If the inversions of the second list are counted by comparing the words themselves, the answer is about alphabetical order, not about the first list. The places in the first list have to be compared.