Simplify editorial !!

Problem:- link

Editorial :- link text

Problem


Find the number of subarrays that have same number of distinct elements as the number of distinct elements in the whole array A[1, N].

Solution


Let L = 1, R = 1, and number of distinct elements in the original array be K <= N.

Maintain a map to count the frequency of the elements, and a set to count the number of distinct elements in the current subarray.

STEP1:

Increment R until the number of distinct elements in range [L = 1, R] equal to K, let this R be R1 <= N. Now since the subarray [L = 1, R1] has K distinct elements, so all the subarrays starting at L = 1 and ending after R1 will also have K distinct elements. Thus add N-R1+1 to the answer.

STEP2:

Now keeping R same, increment L. Now, the subarray is [L = 2, R = R1].
Decrease the frequency of the previous element ie. A[1], and if its frequency = 0, remove it from the set. Repeat the STEP1.

Pseudocode


A = [1, N] // given array

map <int,int> M
set <int> S

R = 1, ans = 0, K = no. of dist. elements

for L = 1 to N:
    while R smaller than or equal to N and SIZE(S) smaller than K: 
        M[A[R]] += 1
        S.insert(A[R])
        R += 1

    if SIZE(S) == K:
	    ans += N-R+1
    M[A[L]] =- 1
    if M[A[L]] == 0:
	    S.remove(A[L])

PRINT(ans)
2 Likes

@code_man look at this pseudo-code.

// replace var's accordingly
int bs(int k,int beg,int end){
	if(beg>end)
		return(0);
	int mid=(beg+end)/2;
	if(a[mid]==k&&!(a[mid+1]==k&&mid+1<=a.size()))
		return(mid);
	else if(a[mid]==k)
		return(bs(a,k,mid+1,end));
	else if(a[mid]>k)
		return(bs(a,k,beg,mid-1));
	else
		return(bs(a,k,mid+1,end));
}
int main(){
    // following 1 based indexing
    // frequency[0]=0;
    // "a" sorted array
    for(i=1;i<=n;i++){
     frequency[i]=frequency[bs(a[i],1,i-1)]+1;
    }
}

Hope it helps!!

Can any one explain given editorial or another method to solve this problem

@c_utkarsh In last lines, it should be M[A[L]]-=1 and if (M[A[L]]==0) s.remove(A[L]). isn’t it ?

1 Like

Yes, thanks for pointing it out. Updated now.

thanks but problem is i dont know c++ (so the concept of set,map) , how can i solve using c lang

checking for all subsets will give TLE O(n^3) ,so how to do in O(n) steps.
P.S:- dont know c++

is there no way to solve without map,vector plz help me out. I have tried really hard :’( plz -/-

To do this without map/set, you can put all elements into another array, sort that array, then keep the frequency table of size n as an array instead of a map. Now you can perform sliding window mentioned above. To update frequency table, you you can binary search the index of A[L] from the other sorted array.

Well, future suggestion just use C++. Most C code will work with a C++ compiler anyway :stuck_out_tongue:

3 Likes

As @hikarico mentioned, you can solve this in C as well, the idea remains the same but the implementation will be more complex. You can refer to following C submission for a different implementation.

https://www.hackerearth.com/submission/7854882/

I would recommend you to learn C++ as its Standard Template Library (STL) is very useful in competitive programming.

1 Like

Im not getting why we need frquency array?

We need frequency array/map because if frequency of an element becomes 0 in the subarray, the number of distinct elements in it decreases by 1.

@c_utkarsh for frequency array its size should be 10^9 ,bcoz value of array
ranges from 1 to 10^9. This much size is not allowed, so how to keep track of frquency of a no. (upto 10^9)

@hikarico i have used ur logic it gives run time error(SIGSEGV) for half test cases
solution :- https://www.hackerearth.com/submission/9085937/

@code_man that’s why you need the binary search part. While traversing through the sorted array from left,binary search the element at the cuurent_index in the left subarray (from starting index to current-1 index). In binary search, find the index of the rightmost occurrence of the current element.

Once you find the index, in your frequency array “f”,
f[current_inde]=f[found_index]+1; (Here I am thinking your frequency array is initialised to zero initially and you will correctly handle the case when the element is found in the left subarray).

O(n) space- frequency updation.

1 Like

can u plz code it in c ,im not understanding from ur code ill dry run with paper pen. literally causing me headache and frustation, u can understand by how long discussion is going on

Above mentioned frequency array finds frequency of elements considering entire sorted array, but algorithm mentioned requires to find frequency of elements of subarray(from L to R-1,which is original unsorted array). So that for each element in these sub array till distinct count equals k in subarray.
So how we will find frequency of elements in given subarray of original array(not sorted) plz help me

@code_man when you want to do as described by @c_utkarsh, M[A[L]]-=1; then you have to binary search the rightmost occurrence of A[L] in sorted array “a” (considering original array- A and sorted -a).And take the frequency value at the searched index and do whatever you want.

I got accepted all test cases except last , where n= 200000 and all its element are same.

my solution :- https://www.hackerearth.com/submission/9127577/

I dont know why it failed to store (200000*200001)/2. I have declared it as unsigned long long count.(same as others who got these test case accepted)
plz last time last case help me plzz