ExpectedValue
SRM 798 · 2021-01-22 · by lazy_fox
Problem Statement
A derangement of the set {1, 2, 3, ..., N} is its permutation with no fixed points, i.e., a permutation P such that for all i, P[i] != i.
For example, the set {1, 2, 3} has two derangements: {2, 3, 1} and {3, 1, 2}.
Given is the
Let the selected derangement be P. We can now view P as a sequence of integers and ask the question: what is the minimum number f(P) of swaps we need to make in order to sort P into ascending order?
For example, the optimum solution for P = {4, 3, 2, 1} involves two swaps: e.g., swap 2 and 3, and then swap 1 and 4.
The optimum solution for P = {2, 3, 4, 1} requires three swaps: e.g., swap 1 with 2 (producing {1, 3, 4, 2}), then 2 with 4, and finally 3 with 2.
Let M = 109 + 7. The expected value of f(P) is a rational number. When written as a reduced fraction f(P) = X/Y, Y and M are relatively prime. Return (X * Y-1) modulo M.
Constraints
- N will be between 2 and 1500, inclusive.
2 Returns: 1
The only derangement in the bag is P = {2, 1}. We need one swap to sort it, so f(P) = 1. Thus, the expected value of f(P) is 1.
3 Returns: 2
As mentioned in the statement, the two derangements in the bag are {2, 3, 1} and {3, 1, 2}. Each of them requires 2 swaps.
73 Returns: 544920339
111 Returns: 112631362
519 Returns: 121109875
4 Returns: 666666674
There are 9 derangements for N = 4. Three of them have f(P) = 2, the other six have f(P) = 3. Thus, the expected value of f(P) is (3*2 + 6*3) / 9 = 24/9 = 8/3. Computing modulo M = 1,000,000,007 we have 3-1 = 333,333,336, and (8 * 333,333,336) modulo M = 666,666,674.
Submissions are judged against all 18 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ExpectedValue with a public method int solve(int N) · 18 test cases · 2 s / 256 MB per case