here is the [Problem].we are given an array. we have to find number of ways to partition array such that mex in each subset is not more than k .
i tried to solve it by first calculating all the ways to partition and then removing the ways which are not valid.
Sample input 1
0 1 2 3 4 0 1 2 5 3
total number of ways to partition are 2^(n-1)=2^9=512;
now i am having difficulty in removing the ways which are not valid.
can anyone help me to explain me this sample input.
: CodeChef: Practical coding for everyone
Let dp[i] represents no.of ways to partition arr[1:i]
Now lets consider last partition cases which ends at i,lets say we last partition is [j:i] ,
Obviously if MEX of [j:i] is >k,then MEX of [j-1:i] is also >k.so we got a monotonous function ,we can apply binary search to find first p such that[p:i] MEX<=k,so now dp[i]=sum(dp[j]) where p-1<j<i
Do this using segment
How to find mex of arr[j:i] in logn complexity ? I mean what to store on each node of segment tree ?
please explain a little bit more ?
all i can think now is persistent segment tree,where each node [i:j] contains number of distinct element values in range[i:j]
So for [j:i] take ith segment tree,and (j-1)th segment tree
and then lets say u are node [a:b],see if mex lies in [a:(a+b)/2] or [(a+b)/2:b]