PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Subhash Sheoran
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming
PROBLEM:
A permutation is K-beautiful if it can be partitioned into K subarrays such that each subarray consists of elements of the same parity, and cannot be partitioned into \lt K subarrays satisfying this condition.
You are given a permutation with some of the elements replaced by 0's. How many ways exist to replace the 0's such that the resulting sequence is a K-beautiful permutation?
EXPLANATION:
The main observation here is that every odd number is essentially the same since we only care about parity. That is, it doesn’t matter whether we replace a 0 with a 1 or a 3 — only whether we replace it with an even number or an odd number. So, first compute E and O: the total number of unused even and odd integers respectively.
This leads to a dynamic programming solution: we need to keep track of where we are, how many subarrays we have created so far, how many odd/even numbers have been used to replace zeros with so far, and what the parity of the previous element is (to know whether its subarray can be extended or not).
Let f(pos, ct, ev, od, par) denote the number of ways to replace zeros in the first pos positions using od odd integers and ev even integers, such that exactly ct maximal subarrays have been created so far, and the parity of the integer placed at pos is par.
This gives us a somewhat simple recurrence:
- First, suppose P_{pos} \neq 0. Then, the parity at this position is fixed, and we don’t do any replacements so ev and od do not change. So,
- If par \neq parity(P_{pos}), then f(pos, ct, ev, od, par) = 0.
- Otherwise, f(pos, ct, ev, od, par) = f(pos-1, ct, ev, od, par) + f(pos-1, ct-1, ev, od, 1 - par). That is, if the previous position had the same parity then the number of maximal subarrays (ct) doesn’t change, and if it had a different parity the number of subarrays increases by 1.
- Now, suppose P_{pos} = 0. There are two cases to consider: replacing this position with an even integer, and replacing it with an odd integer. I’ll discuss the odd case, the even one follows similarly.
- First, note that we have \max(0, O - od + 1) choices for which odd integer to place here (since od-1 were used in previous positions).
- Then, the recurrence looks similar to the above case: either the parity of the previous position is the same (in which case ct doesn’t change), or it is different (in which case ct increases by 1).
- So, f(pos, ct, ev, od, 1) = \max(0, O - od + 1) \cdot (f(pos-1, ct, ev, od-1, 1) + f(pos-1, ct-1, ev, od-1, 0))
Our final answer is, of course, f(N, K, E, O, 0) + f(N, K, E, O, 1).
Now, note that we have around 2N^4 states in our dp. Even with memoization to make transitions \mathcal{O}(1), this results in a \mathcal{O}(N^4) time solution overall, which is too slow.
To speed it up, we can use a somewhat common dp trick: reduce the number of states by looking for a relation between them.
In our case, ev and od are related: note that any relevant state must have ev + od equal to the number of zeros in positions \leq pos (since we must replace every zero).
The number of zeros in a prefix is fixed, and thus knowing one of ev or od immediately tells us the other one. So, instead of having both ev and od in our state, it is enough to have only one of them.
This reduces our number of states to 2N^3, and transitions are still \mathcal{O}(1) so this is fast enough to pass.
TIME COMPLEXITY
\mathcal{O}(N^3) per test case.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define enl '\n'
#define int long long
#define sz(s) (int)s.size()
#define all(v) (v).begin(),(v).end()
mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());
template <typename A, typename B> ostream& operator<< (ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; }
template <typename A, typename B> istream& operator>> (istream& cin, pair<A, B> &p) {cin >> p.first; return cin >> p.second;}
template <typename A> ostream& operator<< (ostream &cout, vector<A> const &v) {cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template <typename A> istream& operator>> (istream& cin, vector<A> &x){for(int i = 0; i < x.size()-1; i++) cin >> x[i]; return cin >> x[x.size()-1];}
template <typename A, typename B> A amax (A &a, B b){ if (b > a) a = b ; return a; }
template <typename A, typename B> A amin (A &a, B b){ if (b < a) a = b ; return a; }
const long long mod = 1e9+7;
const long long inf = 1e18;
void solve() {
int n,k;
cin>>n>>k;
vector<int>p(n);
cin>>p;
int odd = 0,even = 0;
for(auto u:p) {
if(u) {
if(u&1) odd++;
else even++;
}
}
auto find_odd = [&](int i) {
int total = (n+1)/2;
if(total < i+odd or i < 0) return 0LL;
return total-i-odd;
};
auto find_even = [&](int i) {
int total = n/2;
if(total < i+even) {
return 0LL;
}
return total-i-even;
};
vector<vector<vector<vector<int>>>>dp(n+1,vector<vector<vector<int>>>(n+1,vector<vector<int>>(n+1,vector<int>(2))));
dp[0][0][0][0] = 1;
dp[0][0][0][1] = 1;
for(int i=1;i<=n;i++) {
if(p[i-1]) {
if(p[i-1]&1) odd--;
else even--;
}
for(int j=0;j<=n;j++) {
for(int k=1;k<=n;k++) {
if(p[i-1] == 0) {
if(j) dp[i][j][k][0] = find_even(j-1)*(dp[i-1][j-1][k][0]+dp[i-1][j-1][k-1][1])%mod;
dp[i][j][k][1] = find_odd(i-1-j)*(dp[i-1][j][k-1][0]+dp[i-1][j][k][1])%mod;
}
else if(p[i-1]&1) {
dp[i][j][k][1] = (dp[i-1][j][k-1][0]+dp[i-1][j][k][1])%mod;
}
else {
if(j) dp[i][j][k][0] = (dp[i-1][j-1][k][0]+dp[i-1][j-1][k-1][1])%mod;
}
}
}
}
cout<<(dp[n][n/2][k][0]+dp[n][n/2][k][1])%mod<<enl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
//freopen("./testCasesZip/input13.in","r",stdin);
//freopen("./testCasesZip/input13.out","w",stdout);
int testcases = 1;
cin>>testcases;
while(testcases--) solve();
return 0;
}
Editorialist's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7;
ll add(ll x, ll y) {
ll ret = (x + y) % mod;
if (ret < 0) ret += mod;
return ret;
}
ll mul(ll x, ll y) {
x %= mod; y %= mod;
ll ret = (x * y) % mod;
if (ret < 0) ret += mod;
return ret;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, K; cin >> n >> K;
vector<int> p(n+1);
int odds = (n+1)/2, evens = n/2;
for (int i = 1; i <= n; ++i) {
cin >> p[i];
odds -= p[i] & 1;
if (p[i]) evens -= p[i] % 2 == 0;
}
vector dp(n+1, vector(n+1, vector(n+1, vector(2, 0))));
dp[0][0][0][0] = dp[0][0][0][1] = 1;
int zeros = 0;
for (int i = 1; i <= n; ++i) {
if (p[i] == 0) ++zeros;
for (int j = 1; j <= i; ++j) {
for (int k = 0; k <= odds; ++k) {
if (p[i] > 0) {
int par = p[i] % 2;
dp[i][j][k][1 - par] = 0;
dp[i][j][k][par] = add(dp[i-1][j-1][k][1 - par], dp[i-1][j][k][par]);
}
else {
// place odd here
if (k > 0) {
dp[i][j][k][1] = mul(dp[i-1][j][k-1][1], odds - k + 1);
dp[i][j][k][1] = add(dp[i][j][k][1], mul(dp[i-1][j-1][k-1][0], odds - k + 1));
}
// place even here
if (zeros - k <= evens) {
int rem = evens + k - zeros + 1;
dp[i][j][k][0] = mul(dp[i-1][j][k][0], rem);
dp[i][j][k][0] = add(dp[i][j][k][0], mul(dp[i-1][j-1][k][1], rem));
}
}
}
}
}
int ans = 0;
for (int i = K; i <= K; ++i) ans = add(ans, dp[n][i][odds][1] + dp[n][i][odds][0]);
cout << ans << '\n';
}
}
// dp[i][j][k][0/1] -> number of ways of filling 1...i st it can be minimally divided into j segments, and i've used k odd numbers to do so, with the last number being even/odd
