1165. Which Number Is This Ordering
Given an ordering of n distinct values, print its position in the
lexicographic list of all orderings of those values, counting from 1.
3
2 1 3 -> 3 the orderings in order are
1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1
and 2 1 3 is the third
## What most people try first
Generate the orderings in order and count until the given one appears. It is
correct, and it is the wrong shape for the same reason as in problem 1162: at
n = 18 the list has 18! entries, which is 6402373705728000, and the answer
is one number.
## Count what comes before, instead of walking to it
An ordering p is preceded, in lexicographic order, by exactly the orderings
that first differ from it at some position i and are SMALLER there. Fix i.
Such an ordering agrees with p on positions 0 .. i-1, then places at
position i some unused value smaller than p[i], and then arranges the rest
in any of (n - 1 - i)! ways. So the number of them is
(count of unused values smaller than p[i]) * (n - 1 - i)!
Those groups, over all i, are disjoint, because two different i give
orderings that first differ from p at different places. And they cover
everything smaller than p, because an ordering smaller than p has a first
position where it differs and must be smaller there. So the rank is
1 + sum over i of (smaller unused count at i) * (n - 1 - i)!
## Worked out
p = 2 1 3, values 1 2 3
i = 0: unused {1,2,3}, smaller than 2 is {1}, count 1, times 2! = 2
i = 1: unused {1,3}, smaller than 1 is {}, count 0, times 1! = 0
i = 2: unused {3}, smaller than 3 is {}, count 0, times 0! = 0
rank = 1 + 2 + 0 + 0 = 3
## Why it is correct
The argument above is the correctness argument: the orderings smaller than p
are partitioned by the first position at which they differ from p, each part
is counted exactly by that product, and nothing is counted twice because the
first differing position is unique. Adding 1 converts a count of predecessors
into a 1-based position.
## Overflow
The rank reaches 18!, which is 6402373705728000, far past the 2147483647
a signed 32 bit integer holds. 13! is already 6227020800 and passes it, so
both the running total and the factorial table need 64 bits. The total never
exceeds 18! itself, which is comfortably inside a signed 64 bit integer, and
also inside the 53 bits of exact integer arithmetic a double provides, so no
arbitrary precision type is required.
## Cost
O(n^2) with the obvious counting loop, which is 324 steps at n = 18. A
Fenwick tree over the values would make it O(n log n), and at n = 18 that
is slower in practice.
## Related
Problem 1162 is the inverse, turning a position back into an ordering. The same factorial block sizes appear there, divided rather than multiplied.
Constraints - `1 ≤ n ≤ 18` - `-1000 ≤ a[i] ≤ 1000` - All values are distinct.
Input
The first line contains an integer n.
The second line contains n space-separated distinct integers, the ordering to be ranked.
Output
Print one integer, the 1-based position of the given ordering in the lexicographic list of all orderings of its values.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.