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

×

LEMOVIE - Editorial

11
6

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.

This question is marked "community wiki".

asked 17 Feb '14, 15:00

djdolls's gravatar image

6★djdolls
2.2k518484
accept rate: 0%

edited 23 Jun '14, 19:35

admin's gravatar image

0★admin ♦♦
19.8k350498541

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

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

thanks, done.

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

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) akumar33★

thanks, fixed.

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

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) akumar33★

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) djdolls6★

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) sanjeev17793★
showing 5 of 7 show all

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.

link

answered 17 Feb '14, 21:00

freeman92's gravatar image

3★freeman92
2804711
accept rate: 0%

edited 17 Feb '14, 21:05

Thanks for this good paper...

(08 Apr '14, 15:35) abcdexter242★

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

link

answered 18 Feb '14, 22:37

hatim009's gravatar image

3★hatim009
46421122
accept rate: 8%

edited 18 Feb '14, 22:40

That's good. Thanks for the link.

(19 Feb '14, 18:22) haccks2★

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

link

answered 17 Feb '14, 18:45

jangwa's gravatar image

2★jangwa
17229
accept rate: 10%

edited 17 Feb '14, 18:48

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★

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

link

answered 17 Feb '14, 19:21

ranjanvittal's gravatar image

3★ranjanvittal
161
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) ranjanvittal3★

nice explanation thanks

link

answered 18 Feb '14, 13:01

mca_123's gravatar image

4★mca_123
151
accept rate: 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

link

answered 18 Feb '14, 14:51

rohitbansal's gravatar image

2★rohitbansal
1
accept rate: 0%

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

link

answered 18 Feb '14, 14:53

rohitbansal's gravatar image

2★rohitbansal
1
accept rate: 0%

What was n^2k solution for this problem?

link

answered 18 Feb '14, 19:28

kevind's gravatar image

1★kevind
1482312
accept rate: 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 ...

link

answered 21 Feb '14, 19:17

bigredone's gravatar image

2★bigredone
11
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) xpertcoder4★

Oh, I see. Thanks, mate :)

(21 Feb '14, 23:05) bigredone2★
toggle preview
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