The first step is to determine the maximum possible minimum difference. This will always be $\lfloor N/2\rfloor$:
For even $N$, a sample construction is
and for odd $N$, a sample construction is
To show that this is the maximum possible, suppose that a larger difference could be achieved, $d > \lfloor N/2 \rfloor$. Then, consider $\lfloor N/2 \rfloor$. Its neighbors must be at most $\lfloor N/2 \rfloor-d < 0$, or at least $\lfloor N/2 \rfloor+d \ge N$; thus, it is impossible for $d > \lfloor N/2 \rfloor$.
Then, for a specific test case, we can iterate over each of these permutations and check if they work.
When $N$ is even and $K=0$, it turns out that the answer is always two. To show this, first observe that the permutation must alternate between large elements ($\ge N/2$) and small elements ($< N/2$). Suppose, without loss of generality, that the permutation starts with a large element and ends with a small element.
Then, $N/2$ is only at least $N/2$ away from a single element, $0$. Since the start and end of the permutation are the only places where elements are only adjacent to a single element, $N/2$ must be placed at the start, followed by a $0$:
Now, $N/2+1$ can only be adjacent to $0$ and $1$. Thus, it must be placed right after the $0$ (since the end must be small):
We can continue this logic: $N/2+2$ now can only be next to $0$, $1$, or $2$, so it must be placed right after. Thus, assuming that we started with a large element, we can uniquely generate our entire permutation:
If the first element was small, we could just reverse this permutation. Thus, for any even $N$, we can use a linear check to check if both of these permutations work.
Then, small elements can not be adjacent, and similarly big elements can not be adjacent.
Now, suppose the middle element is fixed somewhere. Then, the two elements it is adjacent to must be $0$ and $N-1$.
We can see this by using $N = 13$ as an example. If we fix where $6$ is, we get three general types of permutations:
where a $-$ denotes a small element and a $+$ denotes a big element.
Note that when fixing $6$ to be at an odd index would cause a completely different structure than fixing $6$ to be at an even index, since the two ranges that the permutation splits into have fundamentally different structure.
In this subtask, our middle element is fixed to one of the endpoints. Without loss of generality, assume that the first element must be $\frac{N-1}{2}$, and the next element is $0$.
Thus, our big and small elements must alternate positions, with the third and last element being big.
In this case, we can consider where we put $\frac{N+1}{2}$. Since it can only be adjacent to $0$ and $1$, we know that it must either be at the third or last position, and $1$ must be the next element.
Now, $\frac{N+3}{2}$ must similarly be on either end of the range we do not know, and we can repeat the same logic for the smallest big element left in our range.
We can illustrate this with an example. Consider what happens if $N=13$. WLOG, suppose that our permutation was of the form
where a $+$ denotes a big element and a $-$ denotes a small one. Then, consider where $7$ can be placed. It can only be adjacent to $0$ or $1$, so it must either be placed third or last, and the $1$ next to it:
Similarly, the $8$ and the $2$ must be placed together on either of the ends of the undecided range, up until we decide the entirety of the range. An example permutation might look like this:
where we decided first to place the $7$ on the left, then the $8$ on the right, and so on until we generated the full permutation.
This inspires an $O(N^2)$ dynamic program. Let $dp(l, r)$ be the number of ways to make the range $[l, r]$, if we know that the smallest big element remaining is $N-\frac{r-l}{2}-1$. We can transition by trying to put the smallest big element remaining either at the beginning or end.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
const int MAX_N = 2e3+5;
const ll MOD = 1e9+7;
int t, n;
ll p[MAX_N], dp[MAX_N][MAX_N];
ll t1(int l, int r, int k){
if(l > r) return 1;
if(l == r){
if(k == p[l] || p[l] == -1) return 1;
return 0;
}
ll &ret = dp[l][r];
if(ret != -1) return ret;
ret = 0;
if((k == p[l] || p[l] == -1) & (k-n/2 == p[l+1] || p[l+1] == -1)) ret += t1(l+2, r, k+1);
if((k == p[r] || p[r] == -1) & (k-n/2 == p[r-1] || p[r-1] == -1)) ret += t1(l, r-2, k+1);
ret %= MOD;
return ret;
}
void solve(){
int k; cin >> k;
memset(p, -1, sizeof(p));
int type = -1;
for(int i = 0; i < k; i++){
int a, b; cin >> a >> b;
if(p[a] != -1) assert(false);
p[a] = b;
}
ll ans = 0;
memset(dp, -1, sizeof(dp));
if(p[1] == 0 || p[1] == -1) ans = (ans+t1(2, n-1, n/2+1))%MOD;
memset(dp, -1, sizeof(dp));
if(p[1] == n-1 || p[1] == -1){
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
ans = (ans+t1(2, n-1, n/2+1))%MOD;
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
}
cout << ans << '\n';
}
int main(int argc, const char * argv[]){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> t >> n;
while(t--) solve();
return 0;
}
Suppose, now, that we fix that the "middle" element is at position $i$. Then, we know that the only elements around it can be $0$ or $N-1$. Assume without loss of generality that the $0$ comes before the $\frac{N-1}{2}$ which comes before the $N-1$.
No matter what, we know that $i-2$ must contain a big element, and $i+2$ must contain a small element.
Now, we can do casework on whether $i$ is odd or even.
Case 1: $i$ is even.
In this case, $i-2$, which must contain a big element, must be even, so $0$ must contain a big element.
Similarly, $i+2$ contains a small element, so $N-1$ must contain a small element as well.
Let's say that our left interval $[0, i-2]$ is the "big" interval, and the right interval $[i+2, N-1]$ is the "small" interval.
Similarly to before, we can consider where we put the smallest remaining big element. Since it can only be adjacent to one of the remaining elements we have not placed, it must go on one of the endpoints of our big interval. Repeating this logic, we see that we can run the same dp as described in Subtask 2.
And for the small intervals, it is the same: we consider where we put the biggest remaining small element. It must go on one of the endpoints, and that inspires us to use a very similar dp formulation as before.
To illustrate this, consider an example with $N = 13$, and $i = 4$.
Then, from these assumptions, we know that our permutation must look like:
Then, $5$ must go in one of the endpoints of the "small" range, and so on for $4$ down to $2$. The same analysis holds for the "big" range: $7$ must go on one of the endpoints of the big range, and then same for $8$.
In the end, we can see an example permutation:
where $5$ is put on the left, $4$ on the right, and so on, until we generate the full permutation.
Case 2: $i$ is odd.
In this case, $i-2$, which must contain a big element, must be odd, so $0$ must contain a small element. Similarly, $i+2$ must contain a small element, so $N-1$ must contain a big element.
We can similarly consider where we put the smallest big element. Now, it must always (by the same logic) be at the end of either of our ranges.
Consider another example with $N = 13$ and $i = 5$.
Here, $7$ must either be placed in position $3$ or position $12$, and so we get
Similarly, $8$ must be placed on one of those right endpoints, and ultimately we can generate a permutation such as
where we repeatedly choose which place we put the smallest big element.
Thus, we can create a new $O(N^2)$ dp formulation $dp(l, r)$ which is the number of ways to assign $[0, l]$ and $[i+2, r]$ if the smallest remaining big element is $\frac{N-1}{2}+1+\frac{i-2-l}{2}+\frac{N-1-r}{2}$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
const int MAX_N = 2e3+5;
const ll MOD = 1e9+7;
int t, n;
ll p[MAX_N], dp[MAX_N][MAX_N];
ll t1(int l, int r, int k){
if(l > r) return 1;
if(l == r){
if(k == p[l] || p[l] == -1) return 1;
return 0;
}
ll &ret = dp[l][r];
if(ret != -1) return ret;
ret = 0;
if((k == p[l] || p[l] == -1) & (k-n/2 == p[l+1] || p[l+1] == -1)) ret += t1(l+2, r, k+1);
if((k == p[r] || p[r] == -1) & (k-n/2 == p[r-1] || p[r-1] == -1)) ret += t1(l, r-2, k+1);
ret %= MOD;
return ret;
}
ll t2(int l, int r, int k){
if(p[l+1] == n/2 && r == n) return 1;
if(k > n) return 0;
ll &ret = dp[l][r];
if(ret != -1) return ret;
ret = 0;
if((k == p[l] || p[l] == -1) & (k-n/2 == p[l+1] || p[l+1] == -1)) ret += t2(l+2, r, k+1);
if((k == p[r] || p[r] == -1) & (k-n/2 == p[r+1] || p[r+1] == -1)) ret += t2(l, r+2, k+1);
ret %= MOD;
return ret;
}
void solve(){
int k; cin >> k;
memset(p, -1, sizeof(p));
int type = -1;
for(int i = 0; i < k; i++){
int a, b; cin >> a >> b;
if(p[a] != -1) assert(false);
p[a] = b;
}
ll ans = 0, r = 0;
do{
if(p[0] == n/2){
memset(dp, -1, sizeof(dp));
if(p[1] == 0 || p[1] == -1) ans = (ans+t1(2, n-1, n/2+1))%MOD;
memset(dp, -1, sizeof(dp));
if(p[1] == n-1 || p[1] == -1){
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
ans = (ans+t1(2, n-1, n/2+1))%MOD;
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
}
}
for(int i = 1; i < n-1; i++){
if(p[i] != n/2) continue;
if(p[i-1] != n-1 && p[i-1] != -1) continue;
if(p[i+1] != 0 && p[i+1] != -1) continue;
memset(dp, -1, sizeof(dp));
int w1 = p[i-1] == n-1, w2 = p[i] == n/2, w3 = p[i+1] == 0; p[i-1] = n-1, p[i] = n/2, p[i+1] = 0;
if(i%2 == 1){
ans = (ans+t2(0, i+2, n/2+1))%MOD;
} else{
ll a = t1(i+2, n-1, n/2+1);
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
ll b = t1(0, i-2, n/2+1);
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
ans = (ans+a*b)%MOD;
}
if(!w1) p[i-1] = -1;
if(!w2) p[i] = -1;
if(!w3) p[i+1] = -1;
}
reverse(p, p+n); r ^= 1;
} while(r);
cout << ans << '\n';
}
int main(int argc, const char * argv[]){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> t >> n;
while(t--) solve();
return 0;
}
For full credit, we can fix where the middle element is, and solve for each individual case in $O(N)$.
Let's consider how we can optimize our $O(N^2)$ dp in each case.
Case 1: $i$ is odd.
Consider any constraint on a small element: $p_j = x$. In order for that small element to be $x$, the big element $p_{j+1}$ must have been $x+\frac{N-1}{2}$. Thus, we can view all of the constraints as a constraint on the big elements instead (and if two constraints said different things, then we could just output $0$).
Consider the constraint that minimizes $x$. We must have $x-\frac{N+1}{2}$ big elements placed down before it, and we also know how many of those elements must have been placed on the left interval and how many of those elements must have been placed on the right interval; suppose that $k$ of them must have been placed on the left.
Since how we place the elements smaller than $x$ has no bearing on how we place things in the future, we know that there are $\binom{x-\frac{N+1}{2}}{k}$ ways of placing these down, and once we place them down our intervals shrink.
Then, we can repeat with our second smallest constraint: we know how many must be on the left and how many must be on the right, so we can multiply by the appropriate binomial coefficient.
Thus, our answer in this case would be the product of these of binomial coefficients, which can easily be found in $O(N)$ time.
Another way to think about this case is by considering what actually happens in our dp formulation. In one step, we are essentially walking along a grid. Any constraint is simply just a point on which we need to get to at some point, so the number of permutations is clearly just the product of the corresponding binomial coefficients.
Case 2: $i$ is even.
We will consider only big intervals (analysis for small intervals is completely symmetric).
Consider the index containing the largest element in a big interval. To the left of that index, any small index containing $x$ must be preceded by $x+\frac{N-1}{2}$, and to the right of it, any small index containing $x$ must be followed by $x+\frac{N-1}{2}$.
Thus, every constraint essentially communicated information about where the $(x, x+\frac{N-1}{2})$ pair must be placed.
Suppose we iterate on these possible $x$ in order from small to large. If we know which side of the center we are on, then we know how many of the pairs must be placed on the left and how many of the pairs must be placed on the right, and so we can just multiply the answer by the corresponding binomial coefficient. Thus, it remains to figure out which side of the center we are on.
How do we figure out which side of the center we are on?
If there are two constraints for the same $x$, we automatically know what order they are in, since we have the constraint over the small and big index.
If there are additional constraints after it, we know that all additional constraints must be on the same side of our original constraint as the center. Thus, if we just compare our constraint with the next one, we know which side the center is on.
If there are no additional constraints, it could actually be possible for the center to be in either direction. In this case, we can just consider both directions, adding up the number of ways from each.
The following is an $O(N^2 \log N)$ implementation (sufficient to solve the problem).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
const int MAX_N = 2e3+5;
const ll MOD = 1e9+7;
int t, n;
ll p[MAX_N], f[MAX_N], inv[MAX_N];
ll po(ll a, ll b = MOD-2){
if(b == 0) return 1;
ll x = po(a, b/2);
x = x*x%MOD;
if(b%2 == 1) x = x*a%MOD;
return x;
}
ll c(int n, int k){
if(k > n || k < 0) return 0;
return f[n]*inv[k]%MOD*inv[n-k]%MOD;
}
ll t1(int l, int r, int k){
vector<pii> v;
for(int i = l; i <= r; i++){
if(p[i] == -1) continue;
if(p[i] == n/2) return 0;
if(i&1){
if(p[i] > n/2) return 0;
if(p[i] >= k-n/2) return 0;
v.push_back({p[i]+n/2, i});
} else{
if(p[i] < n/2) return 0;
if(p[i] > k) return 0;
v.push_back({p[i], i});
}
}
sort(v.begin(), v.end());
if(!v.size()) return po(2, (r-l)/2);
ll ans = 1, curr = n/2;
for(int i = 0; i < v.size()-1; i++){
if(v[i].ff == v[i+1].ff){
if(abs(v[i+1].ss-v[i].ss) != 1) return 0;
if(v[i].ss%2 == l%2){
int num = v[i].ff-curr, s = (v[i].ss-l)/2+1;
ans = ans*c(num-1, s-1)%MOD;
curr = v[i].ff, l += 2*s, r -= 2*(num-s);
} else{
int num = v[i].ff-curr, s = (r-v[i].ss)/2+1;
ans = ans*c(num-1, s-1)%MOD;
curr = v[i].ff, l += 2*(num-s), r -= 2*s;
}
i++;
if(i == v.size()-1) return (ans*po(2, (r-l)/2))%MOD;
continue;
}
if(v[i].ss < l || v[i].ss > r) return 0;
if(v[i+1].ss > v[i].ss){
int num = v[i].ff-curr, s = (v[i].ss-l)/2+1;
ans = ans*c(num-1, s-1)%MOD;
curr = v[i].ff, l += 2*s, r -= 2*(num-s);
} else{
int num = v[i].ff-curr, s = (r-v[i].ss)/2+1;
ans = ans*c(num-1, s-1)%MOD;
curr = v[i].ff, l += 2*(num-s), r -= 2*s;
}
}
if(v.back().ss > r || v.back().ss < l) return 0;
if(v.back().ff == k) return ans*c((r-l)/2, (v.back().ss-l)/2)%MOD;
ans = ans*(c(v.back().ff-curr-1, (v.back().ss-l)/2)+c(v.back().ff-curr-1, (r-v.back().ss)/2))%MOD;
return ans*(po(2, k-v.back().ff-1))%MOD;
}
ll t2(int l, int r, int k){
vector<pii> v;
for(int i = l; i < k-1; i++){
if(p[i] == -1) continue;
if(p[i] == n/2) return 0;
if(i%2 == l%2){
if(p[i] < n/2) return 0;
v.push_back({p[i], i});
} else{
if(p[i] > n/2) return 0;
v.push_back({p[i]+n/2, i});
}
}
for(int i = r; i < n; i++){
if(p[i] == -1) continue;
if(p[i] == n/2) return 0;
if(i%2 == r%2){
if(p[i] < n/2) return 0;
v.push_back({p[i], i});
} else{
if(p[i] > n/2) return 0;
v.push_back({p[i]+n/2, i});
}
}
sort(v.begin(), v.end());
ll ans = 1, curr = n/2;
for(int i = 0; i < v.size(); i++){
if(i > 0 && v[i].ff == v[i-1].ff){
if(v[i].ss-v[i-1].ss != 1) return 0;
if(v[i].ss < k){
if(v[i].ss%2 == l%2) return 0;
} else{
if(v[i].ss%2 == r%2) return 0;
}
continue;
}
if(v[i].ss < l || (v[i].ss >= k && v[i].ss < r)) return 0;
if(v[i].ss < k){
int num = v[i].ff-curr, s = (v[i].ss-l)/2+1;
ans = ans*c(num-1, s-1)%MOD;
curr = v[i].ff, l += 2*s, r += 2*(num-s);
} else{
int num = v[i].ff-curr, s = (v[i].ss-r)/2+1;
ans = ans*c(num-1, s-1)%MOD;
curr = v[i].ff, l += 2*(num-s), r += 2*s;
}
}
ans = ans*c((k-2-l+1)/2+(n-1-r+1)/2, (k-2-l+1)/2)%MOD;
return ans;
}
void solve(){
int k; cin >> k;
memset(p, -1, sizeof(p));
for(int i = 0; i < k; i++){
int a, b; cin >> a >> b;
if(p[a] != -1) assert(false);
p[a] = b;
}
if(n%2 == 0){
// if n is even, we can immediately find the answer
vector<int> p2(n, -1);
for(int i = 0; i < n; i++){
if(i%2 == 0) p2[i] = n/2+i/2;
else p2[i] = i/2;
}
int w1 = 1, w2 = 1;
for(int i = 0; i < n; i++){
if(p[i] != -1){
if(p[i] != p2[i]) w1 = 0;
if(p[i] != p2[n-i-1]) w2 = 0;
}
}
cout << w1+w2 << '\n';
return;
}
ll ans = 0, r = 0;
do{
if(p[0] == n/2 || p[0] == -1){
// we fix one of the endpoints to be the middle element
if(p[1] == 0 || p[1] == -1) ans = (ans+t1(2, n-1, n-1))%MOD;
if(p[1] == n-1 || p[1] == -1){
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
ans = (ans+t1(2, n-1, n-1))%MOD;
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
}
}
for(int i = 1; i < n-1; i++){
if(p[i] != n/2 && p[i] != -1) continue;
if(p[i-1] != n-1 && p[i-1] != -1) continue;
if(p[i+1] != 0 && p[i+1] != -1) continue;
// fix i to be the middle element, i-1 to be n-1, and i+1 to be 0
int w1 = p[i-1] == n-1, w2 = p[i] == n/2, w3 = p[i+1] == 0; p[i-1] = n-1, p[i] = n/2, p[i+1] = 0;
if(i%2 == 1){
ans = (ans+t2(0, i+2, i))%MOD;
} else{
ll a = t1(i+2, n-1, n-i/2-1);
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
ll b = t1(0, i-2, n/2+i/2);
for(int i = 0; i < n; i++) if(p[i] != -1)
p[i] = n-1-p[i];
ans = (ans+a*b)%MOD;
}
if(!w1) p[i-1] = -1;
if(!w2) p[i] = -1;
if(!w3) p[i+1] = -1;
}
reverse(p, p+n); r ^= 1;
} while(r);
cout << ans << '\n';
}
int main(int argc, const char * argv[]){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> t >> n;
f[0] = 1; for(int i = 1; i <= n; i++) f[i] = f[i-1]*i%MOD;
inv[n] = po(f[n]); for(int i = n-1; i >= 0; i--) inv[i] = inv[i+1]*(i+1)%MOD;
while(t--) solve();
return 0;
}