EllysReversals
TCO13 Round 1B · 2013-02-19 · by espr1t
TCO13 Round 1B · 2013-02-19 · by espr1t · Simple Search, Iteration, Sorting, String Manipulation
Problem Statement
Problem Statement
Elly has a list of several distinct strings given in the String[] words. She can apply the following operation as many times as she wants (including zero times):
After performing some operations two strings might become equal. If that happens, Elly crosses them out and continues playing her game with the remaining strings only, i.e. they "disappear" from the list. The girl wonders what is the minimal number of strings she can end up with.
For example, suppose she has the strings {"esprit", "god", "redotopc", "odcpoter", "dog"}. The word "redotopc" can be converted to "topcoder" by first reversing all 8 characters and then reversing the first 4. The word "odcpoter" can also be converted to "topcoder" by performing "odcpoter" -> "docpoter" -> "topcoder". At that point the words become equal and disappear, leaving Elly only with {"esprit", "god", "dog"}. This is where she gets stuck: The words "god" and "dog" cannot become equal, because she can only reverse prefixes with even length. Thus, the minimal number of words she can get is 3.
Given her initial strings inString[] words, return an int indicating the minimal number of strings she can be left with.
- Choose one of the words and call it S.
- Choose an even number k between 2 and |S|, inclusive, where |S| is the length of S (thus, chose a prefix with even length).
- Reverse the order of the first k characters of S (thus, reverse the chosen prefix without the rest of the word).
After performing some operations two strings might become equal. If that happens, Elly crosses them out and continues playing her game with the remaining strings only, i.e. they "disappear" from the list. The girl wonders what is the minimal number of strings she can end up with.
For example, suppose she has the strings {"esprit", "god", "redotopc", "odcpoter", "dog"}. The word "redotopc" can be converted to "topcoder" by first reversing all 8 characters and then reversing the first 4. The word "odcpoter" can also be converted to "topcoder" by performing "odcpoter" -> "docpoter" -> "topcoder". At that point the words become equal and disappear, leaving Elly only with {"esprit", "god", "dog"}. This is where she gets stuck: The words "god" and "dog" cannot become equal, because she can only reverse prefixes with even length. Thus, the minimal number of words she can get is 3.
Given her initial strings in
Constraints
- words will contain between 1 and 50 elements, inclusive.
- Each element of words will contain between 1 and 50 characters, inclusive.
- Each element of words will consist only of lowercase letters of the English alphabet ('a'-'z').
- All elements of words will be distinct.
Examples
0)
{"esprit", "god", "redotopc", "odcpoter", "dog"}
Returns: 3
The example from the problem statement.
1)
{"no", "zaphod", "just", "very", "improbable"}
Returns: 5
It is possible that she cannot get rid of any of the words.
2)
{"rats", "live", "stressed", "to", "act", "as", "star", "desserts", "of", "evil", "cat", "sa", "fo", "ot"}
Returns: 0
It is possible that she ends up with zero words.
3)
{"topcoder", "redocpot", "doretopc", "cpotdoer", "harlemshake"}
Returns: 1
Sometimes it is possible to match different words when using a different sequence of operations.
4)
{"iprlzgukfggzg", "bmhxvjbrtkbxy", "khapjiabbny", "nqlwgmcyvdikt",
"nxromtvtpug", "leealcapovm", "ushnxwjczczbmd", "bwhykzupcux",
"xrlboyuwlnsp", "bbjoketeheezfs", "dxfztrldomjqkv", "dkbktqdtgfujcut",
"zfybzyuxgpnt", "ffmsldrdftode", "vopuufksxd", "pqhbsiujwda",
"yhwbkzupcux", "hkbabnapjiy", "zqsqefrrzehtxn", "yovinyguyudmv"}
Returns: 16
Submissions are judged against all 205 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EllysReversals with a public method int getMin(vector<string> words) · 205 test cases · 2 s / 256 MB per case