Problems Base course RU

Vocabulary richness

sliding window hash table counting text editors

A text is a sequence of n words. For each piece of w consecutive words count how many distinct words it has. Find the piece with the most distinct words and the piece with the fewest; if there are several, the leftmost is needed.

The second test is the fourth volume of War and Peace, the third the epilogue (both in the original Russian), the fourth the beginning of the novel in Louise and Aylmer Maude’s translation. Across the whole novel a thousand-word window holds from 353 to 683 distinct words; the most monotonous place is the reasoning about freedom and necessity in the second part of the epilogue.

Input

The first line holds n and w (1 ≤ w ≤ n ≤ 2·10⁵), the second n words of lowercase letters.

Output

Two lines: the largest number of distinct words and the number of the first word of that piece, then the smallest and the number of its first word (words are numbered from one).

Examples

Example 1

Input

9 3
the cat sat on the mat the cat ran

Output

3 1
2 5

Limits

Time · Python: 5000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 7 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

Neighbouring pieces differ by two words: one came in on the right, one went out on the left. What do you need to remember about a piece to tell at once, from these two words, how the number of distinct words changed?

2The idea

The window keeps a counter for each word: how many times it occurs inside. When a word comes in, its counter grows; if it was zero, there is one more distinct word. When a word leaves, its counter decreases; if it became zero, one fewer. Each shift costs two hash table accesses.

3Walkthrough

First fill the window with the first w words, then shift it n − w times, tracking the largest and smallest values. For the answer to be the leftmost, update a record only on a strict improvement.

Deleting a word from the table when its counter becomes zero is not required, but it keeps the table from growing to the size of the text’s whole vocabulary.

3+Solution

4Complexity

O(n) hash table operations and O(w) memory if zero counters are deleted.

5Common mistakes

Recounting each window afresh. O(n·w): almost a hundred million operations in the second test, five billion in the sixth.
A window one word too long or too short. The word that leaves is number i − w, not i − w − 1; check on the example where w = 3.
Not the leftmost piece. On an equal number of distinct words the record is not updated.

Algorithms behind it

TEC Technique Sliding window A window of width w crawls along the data: the answer is corrected by the entering and leaving element in O(1) instead of O(w). O(n) 2 problems DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems