Sortness
SRM 330 · 2006-12-13 · by soul-net
Problem Statement
The sortness of a sequence of distinct numbers is the average of the sortness of each element. The sortness of an element is the number of higher elements that come before it in the sequence plus the number of lower elements that come after it in the sequence. The lower the sortness of a sequence, the closer it is to being sorted. Only a sorted sequence has a sortness of 0.
For example, in the sequence {3,2,1,4,6,7,5,8} the numbers 1,2,3 and 5 have a sortness of 2, numbers 6 and 7 have a sortness of 1 and numbers 4 and 8 have a sortness of 0. The sortness of the sequence is the average of all those sortness values: (2+2+2+2+1+1+0+0)/8 = 1.25.
You will be given a sequence of distinct numbers a as a
Constraints
- a will contain between 1 and 50 elements, inclusive.
- a will contain exactly one occurrence of each integer between 1 and the number of elements in a, inclusive.
{3,2,1,4,6,7,5,8}
Returns: 1.25
The example in the problem statement.
{1,2,3}
Returns: 0.0
A sorted sequence has a sortness of zero.
{5,4,3,2,1}
Returns: 4.0
A reversed sequence has maximum sortness.
{1,5,8,7,9,6,10,12,11,3,4,2}
Returns: 5.166666666666667
{1}
Returns: 0.0
Submissions are judged against all 71 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Sortness with a public method double getSortness(vector<int> a) · 71 test cases · 2 s / 256 MB per case