Stringversions
2022 TCO Parallel 1B · 2022-04-14 · by misof
Problem Statement
Given an array A[0..n-1], an inversion is a pair of indices (i, j) such that i < j but A[i] > A[j].
Inversions are a measure of how sorted the array is. For example, an array of n distinct elements has no inversions at all when sorted in ascending order and the maximum number of inversions when sorted in descending order.
A string can be seen as an array of characters. And as we can compare characters, we can extend the definition of inversions to strings.
For example, the string S = "hello" can be seen as the array S = { 'h', 'e', 'l', 'l', 'o' }. The pair (0, 1) is an inversion because 0 < 1 while S[0] > S[1]. The pairs (0, 2) and (2, 3) are not inversions: in the first case 'h' < 'l' and in the second case 'l' = 'l'. In fact, (0, 1) is the only inversion for this particular string.
You are given the length L and the desired number of inversions N. We are interested in strings of length L that consist of lowercase English letters ('a'-'z') only. Determine whether one of those strings contains exactly N inversions. If yes, return any one such string. If no, return the empty string instead.
Constraints
- L will be between 1 and 500, inclusive.
- N will be between 0 and L*(L-1)/2, inclusive.
5 1 Returns: "hello"
We want a string of length 5 with exactly 1 inversion. As we saw in the problem statement, "hello" is one of many different strings with this property.
7 0 Returns: "xxxxxxx"
We want a string of length 7 with no inversions at all. As shown by our example answer, a string with seven identical characters has this property. The string "pqrstxy" would also be an acceptable answer. The string "billowy" is probably the only meaningful 7-letter English word with this property.
7 21 Returns: "sponged"
This is the maximum number of inversions a string of length 7 can have. Among valid English words the strings "sponged" and "wronged" have this property, but you can also return any other meaningless string with 21 inversions.
27 351 Returns: ""
There are some arrays of length 27 with exactly 351 inversions. However, there is no string of 27 lowercase English letters with this property. (There are some strings of length 27 with 350 inversions.)
1 0 Returns: "z"
Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Stringversions with a public method string create(int L, int N) · 109 test cases · 2 s / 256 MB per case