PROBLEM LINK:
Setter: Shashwat Chandra
Tester: Yash Chandnani
Editorialist: Rajarshi Basu
DIFFICULTY:
Medium
PREREQUISITES:
DP
PROBLEMS:
Consider any way to pair the integers 1 through 2N into N \leq 1000 pairs (A_1,B_1), (A_2,B_2), \ldots, (A_N,B_N) in such a way that each of these integers is present in exactly one pair, A_i \lt B_i for each valid i and A_1 \lt A_2 \lt \ldots \lt A_N. Let’s call such a sequence of pairs a pairing.
For a pairing (A_1,B_1), (A_2,B_2), \ldots, (A_N,B_N), we can create an undirected graph with 2N nodes (numbered 1 through 2N) and the following edges:
- first type: for each valid i, an edge between nodes i and i+1
- second type: for each valid i, an edge between nodes A_i and B_i
This pairing is valid if for each edge (i,i+1) of the first type, there is an edge of the second type (A_j, B_j) which “surrounds” it, i.e. satisfies A_j \le i and B_j \gt i. The cost of a valid pairing is defined as the number of pairs of edges of the second type such that one of these edges is “nested” in the other, i.e. pairs (A_i, B_i) and (A_j, B_j) such that A_i \lt A_j \lt B_j \lt B_i.
Find the sum of costs of all valid pairings. Since this number may be very large, compute it modulo a given prime P.
EXPLANATION:
Part 1
It’s often useful to figure out if a simpler, yet similar problem can be solved, and maybe we can use a similar solution to solve the full problem? Here, let’s try to first figure out how many such sequences can be formed without worrying about the cost and the sum of the costs.
What will be the DP?
The following 2D DP should come naturally:
- dp[i][j] \implies number of ways to form a sequence such that we have processed first i elements and have j numbers still unpaired.
- Transitions: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]*(j+1)
- The first term corresponds to when we do not end any pair at the current position.
- The second term corresponds to when we do decide to end a pair at the current position. Notice that there will be j+1 options. Why? Well, after we pair our current position (which is not included in j+1) with a previous position (of which there are j+1 choices), we are left with exactly j choices, which we needed since we are calculating for dp[i][j].
Extending to a full solution
Now, we try to extend the previous solution to include the costs and their sum as well. Let dpSum[i][j] denote sum of cost of all valid sequences where i and j denotes the same things as in the previous part.
- First, intuition should tell you that the cost should also be easy to simulate - we just have to account for which of the previous positions get paired right? If we assume that the previously unpaired positions are ordered, then if we pair off the k^{th} of them then there will be k-1 positions that are previous to it, and therefore, would cover it entirely, hence adding to the cost.
- Second, notice that our dp[i][j] array is not entirely useless. After all, we need to find sum of costs of all valid sequences. Let’s say that we are trying to add the cost of the last position we are pairing, and we decide that x other pairs will cover it. Then, how many ways can we even reach at this situation? dp[i-1][j+1] right? NOT dpSum[i-1][j+1] since that denotes the total cost till this state, and not the number of ways to reach that state.
So here are the transitions
From these we can figure out the transitions for dpSum[.][.]:
- dpSum[i][j] = dpSum[i-1][j-1] + dpSum[i-1][j+1]*(j+1) + dp[i-1][j+1]*(1+2+3+ … j)
- The first two terms are pretty similar to the transition for dp[.][.]. We still need this to account for the previous costs. The last term is basically adding the new possible costs. We take the sum (1+2+3+ … j) to denote how many ways we can cover the current pairing, as we discussed.
- It is also important to understand that both the terms (2) and (3) are needed, even though they kindof look similar.
- Well, (3) is taking care of what we are adding in the current pairing, and how many sequences are there for which we need to add this cost.
- Term (2) however takes care of the different sums that existed before and all of them also gets added, whichever position we decide on pairing.
- Hence, dpSum[i-1][j+1]*(j+1) since there are j+1 ways to pair the previous positions, and for each of them we add dpSum[i-1][j+1].
- Hence, dp[i-1][j+1]*(1+2+3+… j) since for this current edge, even though it might seem we are counting its contribution in term (2), we are actually not. Term (3) is used to count it’s contribution. The explanation for how to derive this term is already given.
NOTE: Make sure to think about base cases.
SOLUTIONS:
Tester’s Code
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
vector<pair<vector<pii>,set<int>>> v,u;
void pre(){
int n,p;cin>>n>>p;
v.clear(),u.clear();
v.pb(mp(vector<pii>(),set<int>()));
v.back().snd.insert(1);
repA(k,2,2*n){
u=v;
v.clear();
trav(i,u){
trav(j,i.snd){
v.pb(i);
v.back().snd.erase(j);
v.back().fst.pb(mp(j,k));
}
v.pb(i);
v.back().snd.insert(k);
}
}
ll ans = 0;
debug(sz(v));
trav(ii,v) if(sz(ii.snd)==0){
auto i = ii.fst;
int mx = 0;
bool fg=0;
rep(j,sz(i)-1){
mx = max(mx,i[j].snd);
if(mx==2*(j+1)){
fg=1;
}
}
if(!fg){
rep(j,sz(i)) rep(k,j){
if(i[j].fst<i[k].fst&&i[j].snd>i[k].snd) ans++;
if(i[j].fst>i[k].fst&&i[j].snd<i[k].snd) ans++;
}
}
}
cout<<ans%p<<'\n';
}
int n,p;
ll dp[2009][1009];
int f[2009][1009];
void solve(){
cin>>n>>p;
rep(i,2*n) rep(j,n) dp[i][j]=0,f[i][j]=0;
f[1][0]=1;
repA(i,2,2*n){
f[i][0]=1;
repA(j,1,i/2){
if(i!=2*n&&2*j==i) continue;
int k = i-2*j+1;
f[i][j] = (1ll*f[i-1][j-1]*k+f[i-1][j])%p;
dp[i][j] = (dp[i-1][j-1]*k+1ll*f[i-1][j-1]*k*(k-1)/2)%p;
dp[i][j]+=dp[i-1][j];
dp[i][j]%=p;
}
}
cout<<dp[2*n][n]<<'\n';
}
void solve_x(){
pre();
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
int n;cin>>n;
rep(i,n) solve();
return 0;
}