PROBLEM LINK: https://www.iarcs.org.in/inoi/2018/zio2018/zio2018-question-paper.pdf
Editorialist: Huzaifa Mankda
DIFFICULTY: EASY
**PREREQUISITES:**DP, Math, Counting.
PROBLEM:
Given an array of n elements where each element can either be ‘1’ or ‘0’, find the number of ways to make partitions in the array such that in each partition, number of ones is more than or equal to number of zeros.
Simple but not efficient solution:
An array of n elements can be partitioned from n-1 places. Let’s look how.
B[1] | B[2] | B[3] | B[4] | ..... | B[N]
Thus we can see that ‘|’ represents places from where we can partition an array.
The simplest way is to generate all possible partitions and check for number of ones greater than or equal to number of zeros.
Thus simply we can add all such partitions to our answer.
But this is not efficient. Let’s look how.
Since there are n-1 possible places to make partitions, then total number of possible partitions are
2^{n-1}.
Thus for n=8, it is 128 possibilities and for n=9 it is 256 possibilities. Thus above method is very cumbersome for given task.
Efficient Method:
Let’s look at one important observation.
- Let cache[i] denote the number of heavy sequences starting from index i.
- Let’s say we consider a partition from index l to r (such that r<n) and we know the number of Heavy Partitions of subarray from r+1 to n. i.e. we already know cache[r+1].
- Now, count the number of zeros and ones from l to r.
- If number of ones >= number of zeros, then l to r is a valid partition otherwise not.
- So total number of heavy list starting from l to n such that we partition after r is number of ways to form l to r as valid partition (Which is either 1 or 0) * number of heavy list starting from r+1
Thus,
cache[l] ={ Σ cache[j] where j ∈ [l+1,n], if partition is valid
0 , otherwise}
The base case is when we consider the entire array without any partition
Now whenever r is equal to n
Count the number of zeros and ones from l to r.
cache[l] = { 1 , if l to n is valid partition
0 , otherwise }
Thus calculation for sample is as follows:
N=3
B[1]=1, B[2]=0, B[3]=1
cache[1]=0, cache[2]=0, cache[3]=0
Here cache[i] represents number of Heavy Partition array starting at i and ending at n.
Consider l=3
so the list is { [1] } which is heavy. So cache[3]=1
Now Consider l=2
So the list where l=2 and partition is at 2 is { [0] ,[1]} and as we can see [0] is not heavy so add zero
to cache[2].
Now consider when l=2 and i=3 so the list is { [0,1] } and i=n and list [0,1] is heavy
so add 1 to cache[2]. Thus cache[2]=1 now
Now consider l=1 and i=1 list is { [1], [0,1] } as we see [1] is heavy, so add cache[2] to cache[1].
So cache[1]=1 now.
Now consider l=1 and i=2 list is { [1,0], [1] } and [1,0] is heavy so add cache[3] to cache[1]
So cache[1]=2 now.
Now consider l=1 and i=3 so the list is { [1,0,1] } and it is heavy and i=n so add 1 to cache[1]. Thus
cache[1]=3 now.
Now since we are done with computations, let’s look at cache array
cache[1]=3 , cache[2]=1 , cache[3]=1
We want to know the number of Arrays starting at 1 to n whose partitions are all heavy, which is
represented by cache[1]. Hence cache[1] is the required answer.
The cache array for each subtask is as follows:
( a ) N = 8, B = [0, 1, 1, 0, 0, 1, 1, 1]
cache =[ 20, 24, 10, 2, 4, 4, 2, 1 ]
( b ) N = 9, B = [1, 1, 0, 0, 1, 0, 0, 1, 1]
cache=[ 16, 4, 0, 2, 5, 1, 2, 2, 1 ]
( c ) N = 9, B = [1, 0, 1, 0, 1, 1, 0, 1, 1]
cache=[ 96, 24, 36, 12, 12, 6, 2, 2, 1 ]
SOLUTION FOR REFERENCE:
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int b[n+1];
for(int i=1;i<=n;i++){
cin>>b[i];
}
int cache[n+1]={0};
for(int i=n;i>=1;i--){
int zeros=0,ones=0;
for(int j=i;j<=n;j++){
if(b[j]==0)
zeros++;
else
ones++;
if(j==n){
if(ones>=zeros)
cache[i]++;
}else{
if(ones>=zeros){
cache[i]+=cache[j+1];
}
}
}
}
cout<<cache[1]<<"\n";
return 0;
}