PROBLEM LINK:
Author: Dharsan R
Tester: Dharsan R
Editorialist: Dharsan R
DIFFICULTY:
MEDIUM
PREREQUISITES:
HASHING, DYNAMIC PROGRAMMING, COMBINATORICS
PROBLEM:
Given an Array of Integers , Find the number of ways you can split the array into continuous subarrays such that distinct elements in one subarray does not occur in another.
EXPLANATION:
In order to find the total number of ways to split the array with the given constraint, let us first find the splitting of the array A into K continuous subsets S1, S2, …, Sk for some arbitrary K, such that S1 + S2 + … + Sk = A and no subset Si (1 <= i <= K) can be split further and is the smallest possible. Note that the '+' symbol denotes the concatenation symbol here.
To find this, let’s define an map M, which stores the position of the last occurrence of all distinct elements in the array. This can be be achieved in linear time by using Hashing. Next step is to define a DP array P of length N such that P[i] stores the position of the last occurrence of the element A[i] i.e; M[A[i]]. Now the main purpose to use a DP array is to find the all the spitting points in the array.
Now the question is how to achieve this?
For simplicity, let us consider a single subarray S[x:y] (1 <= x <= y <= N) such that the elements of this subarray does not belong to another subarray, which means if an element e ∈ S[x:y], the all the occurrences of the element e in the array should lie in the range [x,y]. The converse is also true, if an element t ∉ S[x:y], the all the occurrences of the element e in the array does not occur in the range [x,y].
But what to do with these analysis?
Lets take an example,
consider an array A = [ 1, 2, 1, 3, 1, 2, 5, 4, 5, 6, 7, 7].
We know that the smallest splitting for this array would be [1,2,1,3,1,2] , [5,4,5] , [6] , [7,7].
The map M of this array will be M = { 1: 4, 2: 5, 3: 3, 5: 8, 4: 7, 6: 9, 7: 11 } (with ‘0’ based indexing).
Then the DP array P = [4, 5, 4, 3, 4, 5, 8, 7, 8, 9, 11, 11].
It can be observed that the certain numbers fall in a particular range, these ranges are our required subsets. To find the range let us define an array T where T[i] stores the maximum element among the first i elements in P.
Then our T array is,
T = [4, 5, 5, 5, 5, 5, 8, 8, 8, 9, 11, 11]
It can be noted here that if T[i] equals i, then the index i is one of the splitting point.
By this we can find all the minimal subarrays of any given array.
Now that we have all the K subarrays, how to find the total number of possible splitting?
We have K subarrays with at this point. Now we can observe that even if we concatenate any two adjacent subarrays, the resulting splitting of the subarrays would still be not violating the constraint that any distinct element should be present in at most one subarray. Since we have K subarrays which means there are K-1 possible concatenations that you can perform. Every choice of either concatenating or not concatenating for each of the K-1 possibilities would result in a possible split. Hence by using combinatorics, we can conclude that there would be 2^{K-1} total possibilities to split the array.
SOLUTIONS:
Setter's Solution
z=10**9 + 7
size=10**6+1
power=[1]*size
for i in range(1,size):
power[i]=(power[i-1]*2)%z
def solve(s,n):
m={}
for i in range(n):
m[s[i]]=i
a=[m[i] for i in s]
m=-1
c=0
for i in range(n):
m=max(m,a[i])
if m==i:
c+=1
return power[c-1]
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
ans=solve(a,n)
print(ans)