The statement was short and simple according to me. I didn't feel like anything else was needed.

Here is my non inclusion-exclusion solution.

Suppose you have $$$N$$$ balls arranged in the top row and $$$N$$$ boxes arranged in the bottom row. Now you need to put $$$i$$$-th ball in $$$P_i$$$-th box such that $$$|P_i-i| \geq X$$$.

So you can have $$$dp$$$ such that $$$dp[i][l][r][mask_1][mask_2]$$$ denotes the number of ways to distribute the first $$$i$$$ balls into first $$$i$$$ boxes such that

• $$$l$$$ boxes in range $$$[1,i-X+1]$$$ are empty
• $$$r$$$ balls in range $$$[1,i-X+1]$$$ have not been put into any box(to be clear we can only considering first $$$i$$$ boxes currently; these balls will be put in some later boxes)
• $$$mask_1$$$ denotes the status of last $$$X-1$$$(range $$$[i-X+2,i]$$$) boxes(whether they are empty or not)
• $$$mask_2$$$ denotes the status of last $$$X-1$$$(range $$$[i-X+2,i]$$$) balls(whether they have been put inside any box or not)

Now for index $$$i+1$$$,

• you have two options for $$$i+1$$$-th ball: either you put this ball in one of $$$l$$$ boxes in range $$$[1,i-X+1]$$$ or decide to put it in later boxes(in this case the status of this ball will get included in $$$mask_1$$$)
• you have two options for $$$i+1$$$-th box: either you put one of the $$$r$$$ ball in range $$$[1,i-X+1]$$$ or decide to put some later ball in this box(in this case the status of this box will get included in $$$mask_2$$$)

After each transition, you update $$$l$$$, $$$r$$$, $$$mask_1$$$ and $$$mask_2$$$

So finally your answer is $$$dp[n][0][0][0][0]$$$

Time complexity is $$$O(N^3 \cdot 4^X)$$$, with low constant factor.

void solve(){ 
    ll n,x; cin>>n>>x;
    dp_(n,n,15,15);
    dp[0][0][0][0]=1;
    ll comp=1;
    for(ll i=1;i<x;i++){
        comp*=2;
    } 
    for(ll i=1;i<=n;i++){
        adp_(i,i,comp,comp);
        for(ll l=0;l<=i-1;l++){
            for(ll r=0;r<=i-1;r++){  
                for(ll mask_1=0;mask_1<comp;mask_1++){  
                    for(ll mask_2=0;mask_2<comp;mask_2++){
                        if(dp[l][r][mask_1][mask_2]==0){  
                            continue;
                        }
                        for(ll give:{0,1}){
                            for(ll take:{0,1}){
                                ll new_l=l,new_r=r,ways=dp[l][r][mask_1][mask_2];
                                ll new_mask_1=2*mask_1+1,new_mask_2=2*mask_2+1;
                                if(take){
                                    ways=(ways*l)%MOD;
                                    new_l--,new_mask_2--;
                                }
                                if(give){
                                    ways=(ways*r)%MOD;
                                    new_r--,new_mask_1--;
                                }
                                if(new_mask_1&comp){
                                    new_l++;
                                }
                                if(new_mask_2&comp){
                                    new_r++;
                                }  
                                if(min(new_l,new_r)<0){
                                    continue;
                                }
                                adp[new_l][new_r][new_mask_1%comp][new_mask_2%comp]+=ways;
                                adp[new_l][new_r][new_mask_1%comp][new_mask_2%comp]%=MOD;
                            }
                        }
                    }
                }
            }
        }
        swap(dp,adp);
    }
    cout<<dp[0][0][0][0]; 
    return;  
}  

Yes, I did think of this way during contest, but could not figure out how to determine the recurrences since bruteforcing 43! (I thought 20 would be sufficient since for X = 3 it depended on previous 5 terms) permutations wasn't feasible. How exactly are you determining the recurrences ?

https://oeis.org/A183244

Could you share your approach? I am not getting the editorial's solution.

Your solution fails when $$$n_1 = 1$$$ or $$$n_2 = 1$$$ or both. Your max1 (or max2) variable will be equal to Integer.MIN_VALUE since max in your BFS will never get updated.

That's because of dp[i][0] and dp[i][M+1], which should be $$$0$$$. If you naively use polynomials, for example dp[i][0] gets (kinda) dp[i-1][-1]+dp[i-1][0]+dp[i-1][1], which does not evaluates to $$$0$$$, eventually destroying the whole polyonimal.

Maybe some example would help

Assume that the boxes are already sorted by $$$h$$$ :

 1 2 7 
 2 4 6 
 3 4 5 
 4 5 6 
 

Consider we are now evaluating box 4. Now we want to check whether there's a box can be fit inside box 4

By using the example above, we can see that box 3 can fits in the box 4

How to do that?

For each of the width, store the minimum depth of a box having that width. Let's store it in an array named $$$X$$$

So in the example above, this array $$$X$$$ will look like this :

1 2 3 4 5 6 7 ....
0 7 0 5 0 0 0 ....

We can now see thst when we evaluate box 4 (which has the width of 5), it's the same of finding minimum of $$$(X_1, X_2, X_3, X_4)$$$

Then we check whether the minimum values is less than box 4's depth. If it is, then we can conclude that there's a box can be fit inside box 4

And since we're gonna updating the $$$X$$$ values each time we evaluate new box and we can also need to find the minimum values of that array, then this task can be solved with segment tree

++ I have checked several times for the same.

unrated beginner contest?

Just updated now!

SegmentTree

I'm not sure if this is the reason, but unordered_map has a big constant factor which is slowing your code down quite a lot. $$$O(n \log^2 n)$$$ is already quite heavy and it's not that surprising that significantly increasing the constant factor TLE's.

Use gp_hash_table or some custom made faster hashtable.

Submission after editing.

actually this test case can never exist because, pi<=i-1 so for example parent of 2 can never be 5