SortInversions
2020 TCO Round 4 · 2020-04-13 · by misof
Problem Statement
Bob had an array that contained the integers from 1 to N, inclusive. He converted each integer into a string. Then, he sorted the array. Finally, he converted each string back into an integer.
Count and return the number of inversions in Bob's final array.
Notes
- A pair of indices (i, j) into an array B is an inversion if and only if (i < j and B[i] > B[j]). In other words, an inversion is a pair of elements such that the bigger element is to the left of the smaller one.
Constraints
- N will be between 1 and 10^9, inclusive.
12 Returns: 24
Bob had the array {1, 2, ..., 9, 10, 11, 12}. He converted the elements to strings: {"1", "2", ..., "9", "10", "11", "12"}. He sorted those strings: {"1", "10", "11", "12", "2", ..., "9"}. He converted everything back to integers: {1, 10, 11, 12, 2, ..., 9}. This array now contains 24 inversions.
7 Returns: 0
199 Returns: 9610
1 Returns: 0
10 Returns: 8
Submissions are judged against all 27 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SortInversions with a public method long long count(int N) · 27 test cases · 2 s / 256 MB per case