MaxOfMin
SRM 800 · 2021-02-08 · by laoriu
Problem Statement
Nam has a permutation P = { P[1], P[2], ..., P[N] } of integers from 1 to N, inclusive.
For any such permutation we can define the following values:
- pmin(k, i) is the minimum of k consecutive elements, starting at index i
- f(k) is the maximum of pmin(k, i) over all valid choices of k consecutive elements
Formally:
- for each k and i such that 1 <= k <= N and 1 <= i <= N-k+1: pmin(k, i) = min{ P[i], P[i+1], ..., P[i+k-1] }
- f(k) = max{ pmin(k, 1), pmin(k, 2), ..., pmin(k, N-k+1) }
Nam has calculated all N values f(1), f(2), ..., f(N) and he has written them on a piece of paper. You are given these values in the
A few days later Nam totally forgot his permutation P. Luckily, he still kept the paper with the sequence F.
Please help him: count all permutations P that correspond to the given F and return that count modulo 998244353.
Constraints
- F will have between 1 and 50 elements, inclusive.
- Each element of F will be between 1 and 50, inclusive.
{3, 1, 1}
Returns: 2
Let's examine all six permutations of the set {1, 2, 3}: P = {1, 2, 3} f(1) = max(1, 2, 3) = 3 f(2) = max(1, 2) = 2 f(3) = max(1) = 1 P = {1, 3, 2} f(1) = max(1, 3, 2) = 3 f(2) = max(1, 2) = 2 f(3) = max(1) = 1 P = {2, 1, 3} f(1) = max(2, 1, 3) = 3 f(2) = max(1, 1) = 1 f(3) = max(1) = 1 P = {2, 3, 1} f(1) = max(2, 3, 1) = 3 f(2) = max(2, 1) = 2 f(3) = max(1) = 1 P = {3, 1, 2} f(1) = max(3, 1, 2) = 3 f(2) = max(1, 1) = 1 f(3) = max(1) = 1 P = {3, 2, 1} f(1) = max(3, 2, 1) = 3 f(2) = max(2, 1) = 2 f(3) = max(1) = 1 We see that there are two permutations that match the given F: the permutations {2, 1, 3} and {3, 1, 2}.
{3, 1, 3}
Returns: 0
As we saw above, for N = 3 there are no permutations with f(3) = 3.
{5, 2, 2, 1, 1}
Returns: 12
The twelve permutations that match this F are precisely the permutations in which P[2] and P[4] are 1 and 2, in either order.
{6, 5, 2, 1, 1, 1}
Returns: 40
{50, 45, 39, 33, 27, 19, 19, 19, 12, 12, 7, 7, 7, 6, 6, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: 364866987
Don't forget the modulo.
{50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Returns: 32990492
Don't forget the modulo
Submissions are judged against all 164 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MaxOfMin with a public method int count(vector<int> F) · 164 test cases · 2 s / 256 MB per case