PROBLEM LINK:Author: Vitaliy DIFFICULTY:EasyMedium 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: It can be seen that PM() is a nondecreasing 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 Now, we insert 3 copies of 2. There are many possible sequences resulting from it. Here are two of them: 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) 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.
This question is marked "community wiki".
asked 17 Feb '14, 15:00
showing 5 of 7
show all

I used the Dynamic Programming approach of "Strongly outstanding elements of multiset permutations" from the paper "Lefttoright maxima in words and multiset permutations by Myers and Wilf". Here is link to my solution 3398934 P.S.: I found the explanation in this paper is easily understood. answered 17 Feb '14, 21:00

Here is the link which helped me to solve this problem http://stackoverflow.com/questions/7692653/googleinterviewarrangementofblocks I used Approach 2 mentioned in the link in which we place numbers in increasing order.... My solution http://www.codechef.com/viewsolution/3421372 answered 18 Feb '14, 22:37

Hi Admin, code(c#) is running fine in my compiler, but on submission I'm always getting runtime error(nzec). can you please provide the case for which its failing. Thanks answered 18 Feb '14, 14:51

http://www.codechef.com/viewsolution/3438932 is the latest solution submitted by me. answered 18 Feb '14, 14:53

last line should be "Finally, the ANSWER is (numPerm[1] + numPerm[2] + ... + numPerm[k])."
thanks, done.
I think, in the "update" function, the way numPerm[r+1] is updated, is wrong. It should be: numPerm[r + 1] += numPerm[r]*t * n;
thanks, fixed.
One more doubt. The array numPerm[0..k] will be initialized with zeroes, right? If that is the case, then the array will remain zero till the end. (unless numPerm[0] is set to 1 in the beginning) In short, can you please suggest the initialization for numPerm?
I think it is implicit that in the beginning when the multiset is empty, numPerm[0] = 1, and numPerm[i] = 0, for i > 0.
Is the loop "for (int r = k  1; r >= 0; r) " should be "for (int r = k ; r >= 0; r) "?? Please explain it.