PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Soumyadeep Pal
Tester: Tejas Pandey, Abhinav Sharma
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Easy-Medium
PREREQUISITES:
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[0] = 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[0]=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[0] = fact[1] = ifact[0] = ifact[1] = 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[1].size() == 0 || left[1][0] != n) cout << "0\n";
else lp[1]++, rp[n]++, cout << solve(1, n, n, left, right, lp, rp) << "\n";
}
return 0;
}