Autocomplete
SRM 846 · 2023-05-22 · by misof
Problem Statement
This problem is inspired by typing using an "autocomplete" feature.
We have a phone. The phone has a standard US keyboard. The 27 keys on the keyboard we are going to use are all the letters ('a' to 'z') and backspace. Additionally, the phone offers up to S suggestions to autocomplete the current word.
The keyboard works as follows: We start with an empty word. As an action the user can press any key on the keyboard. Pressing a letter appends it to the current word. Pressing backspace erases the last letter of the current word. In the special case when the current word is empty, pressing backspace does nothing (but still counts as an action).
Autocompletion works as follows:
- As an action, the user can select any one of the currently offered suggestions. This action replaces the current word with the selected word. (The editing then continues: the user can perform more actions of any type.)
- The cellphone contains a wordlist: a list of all words that can be the result of autocompletion. This list is given in the
String[] L. Elements of L are sorted in decreasing order of priority - i.e., when deciding between two elements of L we always prefer the one with the smaller index. - If the user has currently typed some string X, only words that have X as their proper prefix can be offered as suggestions. (Even if X itself is in the list L, it is not offered as a suggestion when it is already typed completely.)
- If the last action was the press of a letter or the acceptance of an autocomplete suggestion, we simply want to offer the first S matching words from the wordlist as the current autocomplete suggestions. If there are fewer such words, we offer fewer suggestions.
- If the last action was a backspace, we construct the suggestions in two passes:
- Primarily, we want to offer the first S words from the wordlist that are valid suggestions now but weren't valid suggestions before the very last backspace. (E.g., if the current word was "dog" and the user pressed backspace, after that backspace we want to offer suggestions that have "do" but not "dog" as a proper prefix.)
- If we now have fewer than S suggestions, we will fill the remaining ones using the most popular words that were also valid suggestions before the very last backspace. (E.g., if in the previous example S=5 and we found three suggestions using the previous rule, we now add the best two suggestions that have "dog" as a proper prefix.)
- If at this point we still have fewer than S suggestions, we offer fewer than S suggestions.
You are given the above data, the word W we want to type, and the number A of actions. Count all ways of producing exactly the word W by taking exactly A actions. Return that count modulo 10^9 + 7.
Notes
- There is no restriction on words produced during the sequence of A actions. In particular, it is allowed to produce W arbitrarily many times during the process, it is allowed to type letters that are not in W, and produce words that are longer than anything in the wordlist.
Constraints
- W will contain between 0 and 50 characters, inclusive.
- Each character in W will be a lowercase English letter ('a'-'z').
- L will contain between 0 and 50 elements, inclusive.
- Each element of L will contain between 1 and 50 characters, inclusive.
- The total length of all elements of L will not exceed 1000.
- The elements of L will be distinct.
- Each character in L will be a lowercase English letter ('a'-'z').
- S will be between 1 and 5, inclusive.
- A will be between 1 and 50, inclusive.
"topcoder"
{}
1
7
Returns: 0
With no autocomplete suggestions, seven actions aren't enough.
"topcoder"
{}
3
8
Returns: 1
With eight available actions we only have one solution: type the word, letter by letter.
"topcoder"
{}
1
9
Returns: 1
If there are no suggestions, you cannot take an action that accepts a suggestion. There is only one way to produce this word in 9 keystrokes: press backspace with an empty word and then type it.
"topcoder"
{}
1
10
Returns: 235
Type the eight letters. Additionally, at one of the nine available moments, type any letter followed by a backspace. One additional solution other than those: press backspace twice and then type the word.
"topcoder"
{"topcoder"}
3
1
Returns: 1
Immediately accept the only suggestion.
"topcoder"
{"tamale", "tester", "torus", "tomato", "top", "topcat", "topper", "topcoder"}
3
4
Returns: 2
The only two valid sequences of actions: type 't', 'o', 'p', and accept the suggestion "topcoder". (Note that after the third action "top" is no longer offered as a suggestion so you see "topcoder" among the three offered suggestions.) type 't', 'o', accept the suggestion "top", accept the suggestion "topcoder".
"topcoder"
{"topher", "topcat", "topper", "topcoder"}
3
4
Returns: 1
Accept the suggestion "topcat", backspace, backspace, accept the suggestion "topcoder".
"topcoder"
{"talcum","tomato","toe","toenail","topcoder"}
3
3
Returns: 1
If we type 't' and 'o', the three suggestions at that moment will be "tomato", "toe", and "toenail", so this approach cannot produce "topcoder" in just three actions. However, we have a different way: accept the suggestion "toe" and press backspace. After these two actions the current word will be "to" and the offered suggestions will be "tomato", "toe", and "topcoder". (The word "toenail" is currently not offered as a suggestion because it was already a valid suggestion before the backspace. The word "toe" is offered as a suggestion because it was not a valid suggestion when "toe" was the current word.) Thus, the only sequence of actions that works is the following one: accept "toe", backspace, accept "topcoder".
"topcoder"
{"topcoders"}
1
4
Returns: 83
Accept the suggestion, press backspace, type any letter, press backspace: 26 ways. Accept, letter, backspace, backspace: 26 ways. Accept, backspace, backspace, 'r': 1 way. Accept, backspace, accept, backspace: 1 way. Letter, backspace, accept, backspace: 26 ways. Backspace, backspace, accept, backspace: 1 way. Backspace, 't', accept, backspace: 1 way. 't', 'o', accept, backspace: 1 way. Total: 83 ways.
"topcoder"
{"topcoders", "topcoderparadise", "topcodertemplate", "topcoderwinner"}
2
4
Returns: 83
Exactly the same solutions as in the previous example. In particular, note that the following sequence is still valid: accept "topcoders", backspace, accept "topcoders", backspace. After the second action (the backspace) "topcoders" is offered as a suggestion because it was not a valid suggestion before that backspace.
"topcoder"
{"topcoder", "cat", "dog"}
2
4
Returns: 164
One valid sequence of actions that is easy to miss: 't', backspace, backspace, accept the suggestion "topcoder". Note that after 't' and backspace the current word is empty and the two valid suggestions are "cat" and "dog" because the last backspace erased a 't'. Then, the second backspace does nothing. There are 0 words that became valid suggestions after this backspace, so this rule gave us 0 suggestions and we still need two more suggestions. We take the first valid suggestions overall: "topcoder" and "cat".
""
{}
1
14
Returns: 60432638
Don't forget about the modulo. The actual answer for this test case is 3,767,060,459,007.
Submissions are judged against all 104 archived test cases, of which 12 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Autocomplete with a public method int count(string W, vector<string> L, int S, int A) · 104 test cases · 2 s / 256 MB per case