ImproveName
SRM 828 · 2022-04-22 · by misof
Problem Statement
Time limit: 3.5 seconds.
We have an established company called companyName.
We have an issue with the name: it shows too late in alphabetical listings of similar companies, so we don't get all the clients we could.
At the same time, if we just rename the company, we would risk losing many old clients.
The way to go is to just tweak the company name a little: we will select exactly K characters in the company name and rearrange them, while keeping the rest of the name intact. Our goal is to end with any name that is lexicographically smaller than the current name.
For example, if our company name is "TOPCODER" and K = 3, one of the many ways how to improve this name starts by selecting the three vowels.
Rearranging the characters can be imagined as a two-step process:
- First we take the selected characters (in our example: 'O', 'O', and 'E') out, leaving gaps in the string (in our example: "T_PC_D_R").
- Then we reinsert the removed characters back into the gaps - one into each gap, in any order we like. (In our example: we can get either the original "TOPCODER", or "TOPCEDOR", or "TEPCODOR".)
A set of K characters (more precisely, a set of K distinct indices into the company name) is called good if we can improve the company name by rearranging those characters. Count all good sets. Return their count modulo 10^9 + 7.
Constraints
- companyName will contain between 1 and 2,000 characters, inclusive.
- Each character in companyName will be an uppercase English letter ('A'-'Z').
- K will be between 1 and length(companyName), inclusive.
"ABCDE" 2 Returns: 0
There is no way to improve this company name by swapping two of its characters.
"AABCCDEEEFZ" 3 Returns: 0
Again, a company name that cannot be improved.
"EEDDCCBBAA" 3 Returns: 120
Regardless of what three letters we select, it is always possible to make the company name lexicographically smaller. For example, if we choose the first three characters, we can rename the company to "EDEDCCBBAA". Thus, the answer is (10 choose 3).
"TOPCODER" 8 Returns: 1
There is only one way of selecting 8 letters out of 8. This set of eight letters is good: if we can rearrange all eight letters in the name, we can choose between many names that are lexicographically smaller than the original. One of those is "CODERPOT".
"TOPCODER" 3 Returns: 49
Some of the triples of characters are good, others are bad. As we have seen in the problem statement, the three vowels (i.e., characters at 0-based indices 1, 4, 6) form one of those 49 good triples.
Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ImproveName with a public method int improve(string companyName, int K) · 84 test cases · 2 s / 256 MB per case