Connection Status:
Competition Arena > StrIIRec

StrIIRec

SRM 545 · 2011-11-22 · by subscriber

SRM 545 · 2011-11-22 · by subscriber · Dynamic Programming, Greedy, Search
Class Name: StrIIRec
Return Type: String
Method Name: recovstr
Arg Types: (int, int, string)
Problem Statement

Problem Statement

For a given string S of length n an inversion is a pair of integers (i, j) such that 0 <= i < j <= n-1 and S[i] > S[j]. (That is, the character at 0-based index i is greater than the character at 0-based index j.) For example, the string "abcab" has 3 inversions: (1, 3), (2, 3), and (2, 4).

Given are ints n and minInv, and a String minStr. We will consider all strings that are permutations of the first n lowercase English letters. That is, these strings have length n and contain each of the first n letters exactly once. Out of these strings, return the lexicographically smallest string R with the following two properties:

  • The number of inversions in R is at least minInv.
  • The string R is not lexicographically smaller than minStr.
If there is no such string, return an empty String instead.

Notes

  • A String A is lexicographically smaller than a String B if A is a prefix of B or A contains a smaller character at the first position where the Strings differ.

Constraints

  • n will be between 1 and 20, inclusive.
  • minInv will be between 0 and n*(n-1)/2, inclusive.
  • minStr will contain between 1 and n characters, inclusive.
  • Each character in minStr will be one of the first n lowercase Latin letters.
  • All characters in minStr will be unique.
Examples
0)
1
0
"a"
Returns: "a"
1)
2
0
"a"
Returns: "ab"
2)
2
0
"b"
Returns: "ba"
3)
2
1
"a"
Returns: "ba"
4)
2
1
"b"
Returns: "ba"
6)
2
1
"ab"
Returns: "ba"

You must find the lexicographically smallest String that has at least 1 inversion and is not lexicographically smaller than "ab".

29)
11
55
"debgikjfc"
Returns: "kjihgfedcba"

"kjihgfedcba" is the only String that has at least 55 inversions.

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

Coding Area

Language: C++17 · define a public class StrIIRec with a public method string recovstr(int n, int minInv, string minStr) · 206 test cases · 2 s / 256 MB per case

Submitting as anonymous