KthStringAgain
SRM 701 · 2016-10-02 · by Arterm
SRM 701 · 2016-10-02 · by Arterm · Dynamic Programming
Problem Statement
Problem Statement
You are given a String s of length m.
We will now define a collection of exactly 2^m (not necessarily distinct) strings.
The collection is generated by the following pseudocode:
long k.
Imagine that we sorted our entire collection lexicographically.
Find and return the string that will appear k-th in the sorted collection.
(Note that k is a 1-based index.)
start with an empty collection
for each subset X of the set {1,2,...,m}:
take a new string t and initialize it to the given string s
for i = 1,2,...,m:
if X contains i:
reverse the last i characters of t
add the string t to the collection
You are also given a Constraints
- s will consist only of lowercase English letters ('a'-'z').
- The length of s will be between 1 and 50, inclusive.
- k will be between 1 and 2^n, inclusive, where n is the length of s.
Examples
0)
"xyz" 5 Returns: "yzx"
Pseudocode will generate the following strings: "xyz" for X = {} (empty set), "xyz" for X = {1}, "xzy" for X = {2}, "xzy" for X = {1, 2}, "zyx" for X = {3}, "zyx" for X = {1, 3}, "yzx" for X = {2, 3}, "yzx" for X = {1, 2, 3}. Sorted lexicographically collection: "xyz", "xyz", "xzy", "xzy", "yzx", "yzx", "zyx", "zyx". The 5th string is "yzx".
1)
"abc" 1 Returns: "abc"
2)
"abc" 8 Returns: "cba"
3)
"topcoder" 58 Returns: "ooredcpt"
4)
"w" 2 Returns: "w"
Submissions are judged against all 47 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class KthStringAgain with a public method string getKth(string s, long long k) · 47 test cases · 2 s / 256 MB per case