You are not logged in. Please login at www.codechef.com to post your questions!

×

# PROBLEM LINK:

Author: Vitaliy
Tester: Hiroto Sekido, Gerald Agapov
Editorialist: Ajay K. Verma

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]).

O (NK)

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be put up soon.
Tester's solution will be put up soon.

This question is marked "community wiki".

asked 17 Feb '14, 15:00

6★djdolls
2.2k518484
accept rate: 0%

0★admin ♦♦
19.8k350498541

last line should be "Finally, the ANSWER is (numPerm[1] + numPerm[2] + ... + numPerm[k])."

(17 Feb '14, 16:48) 4★

thanks, done.

(17 Feb '14, 17:27) 6★

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;

(17 Feb '14, 18:46) 3★

thanks, fixed.

(17 Feb '14, 18:51) 6★

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?

(17 Feb '14, 18:55) 3★

I think it is implicit that in the beginning when the multiset is empty, numPerm[0] = 1, and numPerm[i] = 0, for i > 0.

(17 Feb '14, 19:02) 6★

Is the loop "for (int r = k - 1; r >= 0; --r) " should be "for (int r = k ; r >= 0; --r) "?? Please explain it.

(08 Jun '14, 01:07)
showing 5 of 7 show all

 8 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. answered 17 Feb '14, 21:00 280●4●7●11 accept rate: 0% Thanks for this good paper... (08 Apr '14, 15:35)
 5 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 answered 18 Feb '14, 22:37 3★hatim009 464●2●11●22 accept rate: 8% That's good. Thanks for the link. (19 Feb '14, 18:22) haccks2★
 0 Would you please upload the program Mr. Ajay K. Verma answered 17 Feb '14, 18:45 2★jangwa 172●2●9 accept rate: 10% 3 We will upload the author's and tester's solution soon. (17 Feb '14, 18:51) djdolls6★ This would better suited as comment. (18 Feb '14, 18:18) haccks2★
 0 isnt it num[r]+=t * m;? answered 17 Feb '14, 19:21 16●1 accept rate: 0% 1 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. (17 Feb '14, 19:29) djdolls6★ thanks a lot (17 Feb '14, 20:29)
 0 nice explanation thanks answered 18 Feb '14, 13:01 4★mca_123 15●1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 http://www.codechef.com/viewsolution/3438932 is the latest solution submitted by me. answered 18 Feb '14, 14:53 1 accept rate: 0%
 0 What was n^2k solution for this problem? answered 18 Feb '14, 19:28 1★kevind 148●2●3●12 accept rate: 0%
 0 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 ... answered 21 Feb '14, 19:17 1●1 accept rate: 0% Though the expression is same, we are here counting number of ways to get that. Lets say we have {4 5} and {2a,2b,2c} where a,b,c just differentiate between 2's. So m=2 and n=3. Now we have three possibility {2a 4 5} {2b 4 5} {2c 4 5} For first set, 2b have 3 places to be put i.e (m+1) now we have {2a 2b 4 5} {2a 4 2b 5} {2a 4 5 2b} So 2c have 4 places to be put i.e (m+2) for every above set possible after putting 2b. so just for 1st set we have {2a 2c 2b 4 5}{2a 2b 2c 4 5}{2a 2b 4 2c 5}{2a 2b 4 5 2c} You can see first two sequences are same(by removing a,b,c) but we will count them. (21 Feb '14, 20:40) Oh, I see. Thanks, mate :) (21 Feb '14, 23:05)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,722
×19
×2

question asked: 17 Feb '14, 15:00

question was seen: 5,428 times

last updated: 23 Jun '14, 19:35