LEMOVIE - Editorial

PROBLEM LINK:

Practice
Contest

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.

11 Likes

Would you please upload the program Mr. Ajay K. Verma

isnt it num[r]+=t * m;?

I used the Dynamic Programming approach of “Strongly outstanding elements of multiset permutations” from the paper “Left-to-right 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.

8 Likes

nice explanation thanks

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

http://www.codechef.com/viewsolution/3438932 is the latest solution submitted by me.

What was n^2k solution for this problem?

Here is the link which helped me to solve this problem http://stackoverflow.com/questions/7692653/google-interview-arrangement-of-blocks
I used Approach 2 mentioned in the link in which we place numbers in increasing order…
My solution http://www.codechef.com/viewsolution/3421372

5 Likes

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.

Hmm, can I ask, why has the new copy (m+2) positions available?
Isn’t like 2,2,-,3… same as 2,-,2,3 …

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.

We will upload the author’s and tester’s solution soon.

3 Likes

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.

No. For each permutation with r steps, we create (t * m) permutations with r steps, that is why we multiply.

In the case of numPerm[r + 1], these are new permutations (r + 1) steps, which resulted from the permutations with r steps in the previous iteration. Hence, we need to add.

1 Like

thanks a lot

This would better suited as comment.