 # HIDPERM - Editorial

Tester: Tejas Pandey, Abhinav Sharma
Editorialist: Kanhaiya Mohan

Easy-Medium

# PROBLEM:

Chef creates a set from a permutation (P_1, P_2, \dots, P_N) of length N, as follows:

• Initially Chef takes a empty set S=\phi, and then for every index i\;(1\le i \le N), Chef insert a pair of integers (l_i, r_i) into S, where 1\le l_i \le r_i \le N and (P_{l_i},P_{l_i+1},\dots, P_{r_i}) denotes the longest subsegment of the permutation with P_i as the maximum element.

You are given a set T containing N distinct pairs of integers. Find the number of different permutations of length N from which Chef can create a set S, which is equivalent to set T. Since the number can be very large, print it modulo (10^9+7).
Note that the elements of the set T may not be given in a particular order.

# QUICK EXPLANATION:

• Start with finding the position of the maximum element. The position of the maximum element is i, iff [1, i-1] and [i+1, N] also exist in the set.
• Let f(L,R) denote the number of different ways to arrange (R-L+1) numbers under given conditions. The answer to our problem is f(1,N). Use recursion to find this value.
• Let i be the position of the maximum element in [L,R], then:
f(L, R) = ( (f(L, i-1) \cdot f(i+1, R)) \% mod \cdot {R-L \choose i-L}) \%mod.
Here, f(L, i-1) and f(i+1, R) are independent to each other. Also, {R-L \choose i-L} denotes the ways in which we can choose the numbers for the first half.

# EXPLANATION:

Observation

The most important observation in this problem would be to note that, if a pair [L, R] exists in the set, then, for the subarray [L, R], the position of the maximum element in the subarray is fixed.

How?

Let us assume that the maximum element occurs at position i, (L \leq i \leq R). We claim that there exists a pair [L, i-1] (L<i \leq R) and a pair [i+1,R] (L \leq i <R). These pairs correspond to the maximum elements in the subarrays [L, i-1] and [i+1,R] respectively.

Amongst all possible values, the i for which the pairs [L, i-1] and [i+1,R] exist in the set, is the position of the maximum element. Note that there would be only one such i since the set of pairs was generated from a permutation of numbers.

Finding the position of the maximum element in a pair

If we check all possible values in a pair [L, R] to look for the position of the maximum element, it would be too slow and result in TLE.

Observe that if the maximum element in [L, R] exists at position i, then, there can be no possible pair with value [L, j] (i \leq j < R). In other words, (i-1) is the maximum value for the right bound among all pairs which start at L and end before R.
Similarly, there can be no possible pair with value [j, R] (L < j \leq i). Thus, (i+1) is the minimum value for the left bound among all pairs which end at R and start after L.

Based on this observation, we can use binary search to find the value of (i-1) or (i+1) and then find i.

Calculating the answer for a given pair

For a given pair [L,R], let i denote the position of the maximum element. We now have two subproblems, finding answers to [L, i-1] and [i+1,R]. This indicates the use of recursion.

Let f(L,R) denote the number of different ways to arrange R-L+1 numbers. Since i is the position of the maximum element, we have two subarrays, [L, i-1] and [i+1,R]. We choose (i-L) elements from remaining (R-L) elements (after excluding element at i) for the first subarray. The elements for the second subarray are assigned simultaneously. We then calculate the answers to both subproblems using recursion. The answer to f(L,R) is nothing but the number of ways of arranging numbers in the first subarray times that of second subarray, times the number of ways of dividing numbers amongst the two subarrays.

Formally, f(L, R) = ( (f(L, i-1) \cdot f(i+1, R)) \% mod \cdot {R-L \choose i-L}) \%mod
Finally, the answer to the problem is nothing but f(1,N).
See setter’s solution for implementation details.

# TIME COMPLEXITY:

Note that we don’t need to visit any pair more than once. Also, for each pair, we run a binary search to find the maximum element’s position. Since there are N pairs and binary search runs in O(logN) complexity, the overall complexity is O(NlogN) per test case.

# SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7; // 998244353;
int powm(int a, int b) {
int res = 1; while (b) {
if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;
} return res;
}

int mult(int a, int b) { return (a * b) % mod;}

const int nax = 2e5 + 10;
int fact[nax], ifact[nax];
void factorial() {
fact = 1;
for (int i = 1; i < nax; i++) fact[i] = (fact[i - 1] * i) % mod;
ifact[nax - 1] = powm(fact[nax - 1], mod - 2);
for (int i = nax - 2; i >= 0; i--) ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
}

int C(int n, int r) {
if (n < r || r < 0 || n < 0) return 0;
return mult(fact[n], mult(ifact[r], ifact[n - r]));
}

const int N = 2e5 + 3; // check the limits

int n;
map<pair<int, int>, int> ranges;
vector <int> lft[N], ri[N];

int recurse(int l, int r) {
if (r < l) return 1;
if (ranges[ {l, r}] == 0) return 0;
if (l == r) return 1;
auto it = lower_bound(ri[l].begin(), ri[l].end(), r);
it--;
int mx = (*it) + 1;
auto it2 = lower_bound(lft[r].begin(), lft[r].end(), l + 1);
if (mx != ((*it2) - 1)) return 0;
int temp = recurse(l, mx - 1) * recurse(mx + 1, r) % mod;
temp = temp * C(r - l, mx - l) % mod;
return temp;
}
void solve(int tc) {
cin >> n;
ranges.clear();
for (int i = 1; i <= n; i++) {
lft[i].clear();
ri[i].clear();
ri[i].push_back(i - 1);
lft[i].push_back(i + 1);
}
for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
ranges[ {l, r}] = 1;
lft[r].push_back(l);
ri[l].push_back(r);
}
for (int i = 1; i <= n; i++) {
sort(lft[i].begin(), lft[i].end());
sort(ri[i].begin(), ri[i].end());
}
cout << recurse(1, n) << '\n';
}

int32_t main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
factorial();
int t;
cin >> t;
for (int i = 1; i <= t; i++) solve(i);
return 0;
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll mod = 1000000007;

ll po(ll x, ll n ){
ll ans=1;
while(n>0){
if(n&1) ans=(ans*x)%mod;
x=(x*x)%mod;
n/=2;
}
return ans;
}

const ll MX=2000000;
ll fac[MX], ifac[MX];

void pre(){
fac=1;
for(int i=1; i<MX; i++) fac[i]= (i*fac[i-1])%mod;
for(int i=0; i<MX; i++) ifac[i]= po(fac[i], mod-2);
}

ll ncr(ll n, ll r){
if(r>n || r<0 || n<0) return 0;
return (fac[n]*((ifac[r]*ifac[n-r])%mod))%mod;
}

void solve()
{
int n;
cin>>n;

int l,r;

int d[n+1] = {0};
set<pair<int,int> > s, st;

for(int i=0; i<n; i++){
cin>>l>>r;
st.insert({l-1,r-1});
l--;
d[l]++;
d[r]--;
}

for(int i=1; i<=n; i++) d[i]+=d[i-1];

vector<pair<int,int> > v(n);
for(int i=0; i<n; i++){
v[i] = {d[i],i};
}

sort(v.begin(), v.end());

map<pair<int,int>, int> m;

s.insert({0,n-1});
m[{0,n-1}]=1;

ll ans = 1;

for(int i=0; i<n; i++){
auto it = s.upper_bound({v[i].second+1,0});
--it;

int l = it->first;
int r = it->second;

if(st.find({l,r})==st.end()){
ans=0;
break;
}

if(m[{l,r}]!=v[i].first){
ans = 0;
break;
}

if(l==r) continue;

ans*= ncr(r-l, v[i].second-l);
ans%=mod;

s.erase(it);

if(l<v[i].second){
s.insert({l, v[i].second-1});
m[{l, v[i].second-1}] = m[{l,r}]+1;
}

if(r>v[i].second){
s.insert({v[i].second+1, r});
m[{v[i].second+1, r}] = m[{l,r}]+1;
}
}

cout<<ans<<'\n';

}

signed main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif

int t = 1;

cin>>t;

pre();

for(int i=1;i<=t;i++)
{
solve();
}

}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define maxn 200007
#define mod 1000000007

ll fact[maxn],ifact[maxn];

ll mpow(ll a, ll b){
ll res = 1;
while(b){
if(b&1) res *= a,res %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return res;
}

void pre(){
fact  = fact = ifact  = ifact = 1;
for(int i = 2;i < maxn;i++){
fact[i] = (fact[i - 1]*i)%mod;
ifact[i] = mpow(fact[i],mod - 2);
}
}

ll comb(ll a,ll b){
ll ans = (fact[a]*ifact[b])%mod;
ans *= ifact[a - b];
ans %= mod;
return ans;
}

ll solve(int l, int r, int n, vector<vector<int>> &left, vector<vector<int>> &right, vector<int> &lp, vector<int> &rp) {
if(l == r) return 1;
if(lp[l] >= left[l].size()) {
rp[r]++;
if(lp[l + 1] >= left[l + 1].size() || left[l + 1][lp[l + 1]] != r) return 0;
lp[l + 1]++;
return solve(l + 1, r, n, left, right, lp, rp);
}
if(rp[r] >= right[r].size()) {
lp[l]++;
if(rp[r - 1] >= right[r - 1].size() || right[r - 1][rp[r - 1]] != l) return 0;
rp[r - 1]++;
return solve(l, r - 1, n, left, right, lp, rp);
}
if(l == r - 1) {
if(left[l][lp[l]] == l && right[r][rp[r]] == r) return 0;
return 1;
}
int nxt = left[l][lp[l]];
lp[l]++;
rp[nxt]++;
if(nxt + 1 != right[r][rp[r]] - 1) return 0;
lp[nxt + 2]++;
rp[r]++;
return (((solve(l, nxt, n, left, right, lp, rp)*solve(nxt + 2, r, n, left, right, lp, rp))%mod)*comb(r - l, nxt - l + 1))%mod;
}

int main() {
int t;
cin >> t;
pre();
while(t--) {
int n; cin >> n;
vector<vector<int>> left(n + 1), right(n + 1); vector<int> lp(n + 1, 0), rp(n + 1, 0);
for(int i = 0; i < n; i++) {
int l, r; cin >> l >> r;
left[l].push_back(r);
right[r].push_back(l);
}
for(int i = 1; i <= n; i++) {
sort(left[i].rbegin(), left[i].rend());
sort(right[i].begin(), right[i].end());
}
if(left.size() == 0 || left != n) cout << "0\n";
else lp++, rp[n]++, cout << solve(1, n, n, left, right, lp, rp) << "\n";
}
return 0;
}

4 Likes

Is there a proof for choosing i-L elements out of R-L elements or this is simply because we are given a permutation so we can always arrange any of these chosen elements as we just need to make sure we put max element among chosen elements in correct place?
Am i right or wrong?

Also in this part of setter’s solution:

for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
ranges[ {l, r}] = 1;
lft[r].push_back(l);
ri[l].push_back(r);
}

What does this thing do?

lft[r].push_back(l);
ri[l].push_back(r);