LEMOVIE - Editorial

editorial
, , ,
6

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

7

CodeChef: Practical coding for everyone is the latest solution submitted by me.

8

What was n^2k solution for this problem?

9

Here is the link which helped me to solve this problem algorithm - Google Interview: Arrangement of Blocks - Stack Overflow
I used Approach 2 mentioned in the link in which we place numbers in increasing order…
My solution CodeChef: Practical coding for everyone

5 Likes
10

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 …

11

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

12

thanks, done.

13

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;

14

thanks, fixed.

15

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

3 Likes
16

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

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

18

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
19

thanks a lot

20

This would better suited as comment.

21

That’s good. Thanks for the link.

22

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.

23

Oh, I see. Thanks, mate :slight_smile:

24

Thanks for this good paper…

25

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