PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Prasant Kumar
Tester: Aryan, Satyam
Editorialist: Devendra Singh
DIFFICULTY:
2533
PREREQUISITES:
Dynamic programming
PROBLEM:
You are given an array A of size N.
A partitioning of the array A is the splitting of A into one or more non-empty contiguous subarrays such that each element of A belongs to exactly one of these subarrays.
Find the number of ways to partition A such that the parity of the sum of elements within the subarrays is alternating. In other words, if S_i denotes the sum of the elements in the i-th subarray, then either
- S_1 is odd, S_2 is even, S_3 is odd and so on.
- or S_1 is even, S_2 is odd, S_3 is even and so on.
For example if A = [1, 2, 3, 3, 5]. One way to partition A is [1, 2] [3, 3] [5]. Another way to partition A is [1] [2] [3] [3, 5]. Note that there exists more ways to partition this array.
Since the answer may be large, output it modulo 998244353.
QUICK EXPLANATION
Let dp[i][parity] represent the number of valid partitions of Prefix P_i such that the last subarray chosen has parity of the sum as parity. Let sum[i] represent the sum of first i elements of the A.
Initialize dp[0][0]=1 and dp[0][1]=1
Case 1: sum[i] is even.
- dp[i][0]= \underset{sum[j]|2}{\sum^{i-1}_{j=0}}\,dp[j][1]
- dp[i][1]= \underset{sum[j]\nmid2}{\sum^{i-1}_{j=0}}\,dp[j][0]
Case 2: sum[i] is odd.
- dp[i][1]= \underset{sum[j]|2}{\sum^{i-1}_{j=0}}\,dp[j][0]
- dp[i][0]= \underset{sum[j]\nmid2}{\sum^{i-1}_{j=0}}\,dp[j][1]
EXPLANATION:
Let us calculate the number of valid partitions of A when a fixed prefix P_i (array formed by first i elements of A) is the first subarray of the partition. Let the sum of elements of P_i be even. Then the problem is reduced to finding the number of valid partitions of array B formed by the remaining N-i elements (other than P_i) of array A without changing the order of the elements and starting with the first subarray of the partition having odd sum.
The case when the sum of elements of P_i is odd is similar except now the problem is reduced to finding the number of valid partitions of array B starting with the first subarray of the partition having even sum.
This problem has both optimal substructure property and overlapping subproblems. These kind of problems can be solved using dynamic programming.
Let dp[i][parity] represent the number of valid partitions of Prefix P_i such that the last subarray chosen has parity of the sum as parity. Let sum[i] represent the sum of first i elements of the A.
Initialize dp[0][0]=1 and dp[0][1]=1
Case 1: sum[i] is even.
- dp[i][0]= \underset{sum[j]|2}{\sum^{i-1}_{j=1}}\,dp[j][1] \:i.e. sum of all valid partitions till now such that the last chosen subarray of these partitions has odd sum and the sum of all elements in the partition is even.
- dp[i][1]= \underset{sum[j]\nmid2}{\sum^{i-1}_{j=1}}\,dp[j][0] :i.e. sum of all valid partitions till now such that the last chosen subarray of these partitions has even sum and the sum of all elements in the partition is odd.
Case 2: sum[i] is odd.
- dp[i][1]= \underset{sum[j]|2}{\sum^{i-1}_{j=1}}\,dp[j][0] \:i.e. sum of all valid partitions till now such that the last chosen subarray of these partitions has even sum and the sum of all elements in the partition is even.
- dp[i][0]= \underset{sum[j]\nmid2}{\sum^{i-1}_{j=1}}\,dp[j][1] :i.e. sum of all valid partitions till now such that the last chosen subarray of these partitions has odd sum and the sum of all elements in the partition is odd.
These sums can be maintained using just four variables. The answer would be dp[N][0]+dp[N][1] For details of the implementation see the code attached below.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
#define int long long
#define endl "\n"
using namespace __gnu_pbds;
const int sz=2e5+10;
int arr[sz];
int n;
int dp[sz][3][3];
int mod=998244353;
int solve(int i,int prev,int cur){
if(i+1==n){
return (prev != ((cur+arr[i])%2));
}
if(dp[i][prev][cur] != -1){
return dp[i][prev][cur];
}
int ans=solve(i+1,prev,(cur+arr[i])%2);
if(prev != ((cur+arr[i])%2)){
ans+=solve(i+1,(cur+arr[i])%2,0);
}
return dp[i][prev][cur]=ans%mod;
}
signed main(){
//
// freopen("chef12.txt","r",stdin);
// freopen("chef12_output.txt","w",stdout);
ios_base::sync_with_stdio(0) , cin.tie(0);
int t;cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=0;i<n+5;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
dp[i][j][k]=-1;
}
}
}
// dp(i,parity_of_sum_of_pervious_block, parity_of_current_ongoing_sum);
cout<<solve(0,2,0)<<endl;
}
return 0;
}
Tester's Solution
// #pragma GCC optimize("O3")
// #pragma GCC target("popcnt")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;
const ll MAX=500500;
void solve(){
ll n; cin>>n;
vector<ll> a(n+5),sum(n+5,0);
for(ll i=1;i<=n;i++){
cin>>a[i];
sum[i]=(sum[i-1]+a[i])%2;
}
map<ll,map<ll,pair<ll,ll>>> direct;
direct[0][0]={0,1};
direct[1][0]={1,1};
direct[0][1]={1,0};
direct[1][1]={0,0};
vector<vector<ll>> dp(5,vector<ll>(5,0));
ll val=0;
for(ll i=1;i<=n;i++){
val=0;
vector<vector<ll>> now=dp;
for(ll j=0;j<2;j++){
auto it=direct[sum[i]][j];
val+=dp[it.f][it.s];
now[sum[i]][j]+=dp[it.f][it.s];
now[sum[i]][j]%=MOD;
}
val++;
now[sum[i]][sum[i]]++;
swap(dp,now);
}
val%=MOD;
cout<<val<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 998244353;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n;
cin >> n;
vll v(n);
for (int i = 0; i < n; i++)
cin >> v[i], v[i] %= 2;
ll p[n + 1], dp[2],oddend[2], evenend[2];
memset(dp, 0, sizeof(dp));
memset(oddend, 0, sizeof(oddend));
memset(evenend, 0, sizeof(evenend));
memset(p,0,sizeof(p));
dp[1] = dp[0] = 1;
evenend[0] = oddend[0] = 1;
for (int i = 1; i <= n; i++)
p[i] = p[i - 1] + v[i - 1];
for (int i = 1; i <= n; i++)
{
if(p[i]%2==0)
{
dp[0]=oddend[0];
dp[1]=evenend[1];
evenend[0]+=dp[0];
oddend[0]+=dp[1];
}
else
{
dp[0] = oddend[1];
dp[1] = evenend[0];
evenend[1]+=dp[0];
oddend[1]+=dp[1];
}
dp[0] %= mod;
dp[1] %= mod;
evenend[0]%=mod;
evenend[1]%=mod;
oddend[0]%=mod;
oddend[1]%=mod;
}
cout << (dp[0] + dp[1]) % mod << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}
.
.