PROBLEM LINK:
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).
Solving this, you will get that the time complexity turns out to be \mathcal{O}(n \, log \, n)