MADHAT - Editorial

combinatorics
cook73
easy-medium
editorial
madhat
maths

#1

PROBLEM LINK:

Practice
Contest

Author: Alei Reyes
Tester: Hasan Jaddouh
Editorialist: Praveen Dhinwa

DIFFICULTY:

easy medium

PREREQUISITES:

combinatorics, recursion, maths

PROBLEM:

You are given an array a of size n. You have to find number of permutations p of size n satisfies the following properties.

  • For each i, let j > i be the maximum index such that all the elements in the range [i + 1, j - 1] are less than p_i. a_i denotes the number of such integers in the range, i.e. j = i + a _i + 1.

EXPLANATION:

Let us say we are at some index i. Let j = i + a_i + 1. We should have all the elements in the range [i + 1, j - 1] to be less than a_i and the element at a_j should be greater than a_i. In other words, j is the first index greater than i such that p_j > p_i.

If we can find the position i where the largest value of p_i should be present, then we can divide the problem into two similar recursive formulations. The two subproblems to solve will be for indices < i (left partition) and the other for indices > i (right partition). Note that the largest element is p_i, so we can select any of the i - 1 elements out of the n - 1 remaining numbers (i.e. all minus the largest element which is already selected, the one at index i) for the left partition. Number of ways of doing this selection will be given by \dbinom{n - 1}{i - 1}.

Let us see the pseudo code for this to understand details.

solve(L, R):
// Base case
if (L > R) return 1;
i = findIndexWhereLargestPValueShouldBe(L, R);
return Combination(R - L, i - 1) * solve(L, i - 1) * solve(i + 1, R)

Now, how do we find the position i, where the largest value of p_i should be present for a given range [L, R].

Notice that if P_i is the largest element in the range [L, R], then all the elements at index j > i should be less than P_i. So i + a_i = R + 1. Note that there might be more than one such i's, you can select the left most of them. This is due to the fact that if there exists two candidate i_1, i_2, such that i_1 + a_{i_1} = R + 1 and i_2 + a_{i_2} = R + 1, then P_{i_2} can never be greater than P_{i_1}, otherwise the value of P_{i_1} will be less than required and the condition i_1 + a_{i_1} = R + 1 won’t be satisfied.

So, we now have to find left most index i in a given range, such that i + a_i is equal to some given value. This can be done using binary search. Notice that i + a_i can go at most 2 * n. So, we create sorted lists of indices of size 2 * n, such that vec[v] denotes the indices i in the sorted order such that i + a_i = v.

Now, for a given query for range [L, R] and a value v, we can do a binary search in the sorted array vec[v] to find first index i such that it belongs to range [L, R].

Time Complexity

Let T(n) denote the time complexity for solving the problem for given range [L, R] such that R - L + 1 = n, i.e. for solving n elements. We can write the following recurrence relations for T(n).

T(n) = T(i) + T(n - i) + \mathcal{O}(log \, n) ext{ for } n > 1
T(1) = \mathcal{O}(1)

Solving this, you will get that the time complexity turns out to be \mathcal{O}(n \, log \, n)

Tester’s Solutions:

Setter’s solution
Tester’s solution


#2

Can u please explain a bit more about what is a_i and p_i in the explanation?


#3

I couldn’t figure out bug in my code.It’s giving runtime error.Please help.
https://www.codechef.com/viewsolution/11228802


#4

deepak_kumar94, probably stack overflow. I had a runtime error too, switched to a manual stack (just put [lt, rt] pairs in a vector and replaced recursion with a loop) and it got accepted.


#5

thanks al13n for help.


#6

how can we say that i + ai can go atmost 2n?


#7

How can there be more than one i’s while finding the max element? Give an example


#8

Can somebody help me in debugging my code? I have used a slightly different approach than the solution given above.

P.S.- I have checked my code for pretty long inputs(n>100) and compared it with an accepted solution, and my code produces correct answer every single time.

link text

I would try to explain my solution roughly. Suppose n=20, and the numbers are

4 3 2 1 0 3 2 1 0 6 5 4 3 2 1 0 2 1 0 0

First, i check whether for all i, either A*=A[i+1]+1 or A*=0. If this is not the case, answer is 0. Otherwise, i store the lengths of decreasing segments and their pref-sums. In this case, it is

Vector v={5,4,7,3,1}
Vector w={5,9,16,19,20}

And finally I calculate the answer using

for i:1 to w.size()-1
ans=ans* (w*-1)C(w[i-1])

Hope this helps !!


#9

Can be done in O(N) time using stack, similar to [Largest Rectangular Area in a Histogram problem][1] .


[2]


  [1]: http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
  [2]: https://www.codechef.com/viewsolution/11225928

#10

Could you please elaborate on the 2*n part?As far as my understanding goes, if(i+ai >= n ) assuming array is 0 indexed then 0 permutations are possible.


#11

my solution does not do binary search as described . Instead it does a linear search for the leftmost i in a given range such that i+ai is equal to given value. So the complexity should be O(n*n).
It gives AC verdict.
https://www.codechef.com/viewsolution/11229084
Should it not TLE for the case when all the elements of the array are 0.


#12

my code is giving segmentation fault i couldn’t figure out the reason please look at the code link


#13

@admin …Both the links contain only the tester’s solution.


#14

My solution is getting a runtime error but works fine for the cases on my device
https://www.codechef.com/viewsolution/11583683
Please help


#15

Can you please point out the paragraph which is unclear? I will try expanding !!


#16

The second line in the Problem Statement :
For each i, a_i should denote the maximum index j>i such that all the elements in the range [i+1,j−1] are less than p_i.


#17

I changed this statement to be precise. Please check !!


#18

Thank you!