PROBLEM LINK:
Author: Vitaliy
Tester: Hiroto Sekido, Gerald Agapov
Editorialist: Ajay K. Verma
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic programming, Combinatorics
PROBLEM:
Given an array A of N integers, and an integer k, find how many permutations of the array exist in which “prefix maximum” function takes at most k steps.
QUICK EXPLANATION:
Start with an empty multiset of elements, and add the array elements into it in decreasing order, while maintaining the number of permutations that can be obtained from the elements of the multiset having exactly r prefix maximum steps for all r <= k.
EXPLANATION:
For a given array A of size N, we define the “prefix maximum” function PM as follows:
PM(i) = max(A[0], A[1], …, A[i]).
It can be seen that PM() is a non-decreasing function. Moreover, the function behaves like a step function, i.e., its value increases at some point, then remains constant for a while, until the next step occurs, when it increases again and so on. For any array, the function will have at least one step, and at most N steps, where N is the size of the array.
The problem asks that given an array A of size N, how many permutations of it have k or fewer steps in their PM function.
Adding elements in decreasing order:
Suppose we have a sequence of m elements whose PM function takes exactly r steps. Now, we insert n copies of an element x into this sequence, where x is smaller than all elements of the original sequence. What is the number of steps in the PM function of the new sequence? Let us see an example.
original sequence: 4, 5, 3, 8, 6, 3, 11
PM function: 4, 5, 5, 8, 8, 8, 11
number of steps: 4
Now, we insert 3 copies of 2. There are many possible sequences resulting from it. Here are two of them:
2, 2, 4, 5, 3, 2, 8, 6, 3, 11
4, 5, 2, 3, 2, 8, 6, 2, 3, 11, 2
In the first case number of steps increases from 4 to 5, while in the second case the number of steps remain the same. In other words, if any of the copies of the new element comes in the beginning, then the number of steps will increase by one, otherwise the number of steps will remain the same.
Now, let us find out in how many ways we can insert these new copies such that the number of steps increase. For this, one of the new elements must end up at the beginning of the new sequence. This can be any of the n copies, i.e., there are n ways to pick this element. After inserting this the sequence will be
2, 4, 5, 3, 8, 6, 3, 11
We still need to insert the remaining copies of the new elements. For the next copy, there are exactly (m + 1) positions available, where it can be placed
2,-, 4, -, 5, -, 3, -, 8-, 6, -, 3, -, 11, -
The copy after that will have (m + 2) positions available, and so on.
Hence, we can insert these new copies in exactly (n * (m + 1) * (m + 2) * … * (m + n - 1)) ways such that the number of steps increase by one.
In a similar way, we can show that there are exactly (m * (m + 1) * (m + 2) * … * (m + n - 1)) ways of inserting the new copies such that the number of steps remain the same.
Next, we will show how to use this result to solve our problem.
Dynamic programming approach:
First, we split the element of the array into classes, where the elements in each class have the same value. For array A = {4, 5, 3, 8, 6, 3, 4, 11}, there will be 6 such classes: {3, 3}, {4, 4}, {5}, {6}, {8}, {11}.
Next, we start with an empty multiset and add theses classes into the set in decreasing order of value. At any point we maintain the number of permutations of the multiset which have exactly r steps in their PM function, for all r <= k. We store this value in numPerm[r], and update it as we insert new classes.
Suppose at some point the size of the multiset is m, and we add a new class which has n copies of the same element, then the values in the numPerm can be updated according to the formulae derived in the previous section. More formally,
numPerm[r + 1] += numPerm[r] * n * (m + 1) * (m + 2) * … * (m + n - 1)
numPerm[r] *= m * (m + 1) * (m + 2) * … * (m + n - 1)
Since the term (m + 1) * (m + 2) * … * (m + n - 1) is the same for all r, we can compute it once, and reuse it. The following code shows how to update the numPerm, when a new class is inserted.
// m is the size of existing multiset, and
// n copies of the new element are being inserted,
// which is smaller than all elements of the current multiset.
void update(int &m, int n) {
int t = 1;
for (int i = m + 1; i < m + n; ++i)
t *= i;
for (int r = k - 1; r >= 0; --r) {
numPerm[r + 1] += t * numPerm[r] * n;
numPerm[r] *= t * m;
}
// update the size of the multiset.
m += n;
}
Finally, the answer is (numPerm[1] + numPerm[2] + … + numPerm[k]).
TIME COMPLEXITY:
O (NK)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution will be put up soon.