Connection Status:
Competition Arena > SubstringReversal2

SubstringReversal2

Cognizance - Insomnia · 2019-04-11 · by Vasyl[alphacom]

Cognizance - Insomnia · 2019-04-11 · by Vasyl[alphacom] · Dynamic Programming, String Manipulation
Class Name: SubstringReversal2
Return Type: String
Method Name: solve
Arg Types: (string, long long)
Problem Statement

Problem Statement

You are given a string S of length N. Consider an even-sized subset of {1, 2,..., N}. Say the subset is { p1, p2,.., p2k} such that p1 < p2 < ... < p2k. Now we'll construct a new string from S as follows : reverse the substring from p(2i-1) to p(2i) (inclusive) for each i from 1 to k. Now consider the multiset of strings which can be built in this method by choosing all even-sized subset of {1, 2,..., N}. You have to find the Kth lexicographical string that can be built. It is guaranteed that such a string exists.

Say N = 8, and let's choose a subset, say {1, 3, 6, 8}. Then we reverse the substrings S[1 : 3] and S[6 : 8]. (1-based indexing)


For example, for the string "abcd", the following strings can be built :
abcd
abdc
acbd
adcb
bacd
badc
cbad
dcba
The 3rd lexicographical string is acbd.

Notes

  • Given two strings A and B of equal length, we say that A is lexicographically smaller than B if A has a smaller character than B at the first position where they differ.
  • It's guaranteed that such a string will exist.

Constraints

  • S will contain between 1 and 200 elements, 'a'-'z'.
  • K will be between 1 and 1018.
Examples
0)
"abcd"
6
Returns: "badc"

For the string "abcd", the strings generated are "abcd", "abdc", "acbd", "adcb", "bacd", "badc", "cbad" and "dcba". Among them the 6th lexicographic string is "badc".

1)
"topcoder"
40
Returns: "otpdocre"
2)
"jivfdgznwj"
116
Returns: "ijvdfgjwnz"
3)
"jycirusfrekgpbu"
15994
Returns: "yjricusrfkeubpg"
4)
"omasiyswsbsweyascjytiymav"
8753020
Returns: "oamyissswwsbayesjctyimyav"
16)
"aabc"
2
Returns: "aabc"

For the string "aabc", the strings generated are "aabc", "aabc", "aacb", "aacb", "abac", "acba", "baac" and "cbaa". Among them the 2nd lexicographic string is "aabc".

Submissions are judged against all 18 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SubstringReversal2 with a public method string solve(string S, long long K) · 18 test cases · 2 s / 256 MB per case

Submitting as anonymous