Sub-Sequence Count

So, here is the solution, you store each element as you see in a map.
Every-time, for each element(say,‘x’) , before inserting it :slight_smile: you apply lower-bound function on map for x+k and x-k; and it is solved :slight_smile:

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int k;

map<int,int> mp;
int solve(int A[],int beg,int end1)
{
int count1=0;
if(beg==end1) return 0;
if(abs(A[end1]-A[beg])<=k){
auto it = mp.find(end1);
if(it==mp.end())
{
count1++; mp.insert({end1,beg});
}
else if(it->second!=beg){
count1++; mp.insert({end1,beg});
}

}
 count1+= solve(A,beg+1,end1);
 count1+= solve(A,beg,end1-1);
 return count1;

}

int main()
{
int n;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++) cin>>A[i];
int t = solve(A,0,n-1);
cout<<t+n<<endl;

}
can you tell me this is correct or not?? i am not sure about large inputs.

@karangreat234 Can you please explain the concept a bit more :grimacing:

1 Like

@gagangaur Bro can please explain me how to apply sliding window concept here and if possible share the code it would help alot.

@gagangaur Bro can please explain how sliding window is used here and share the code if possible.

Sorry @rk_221b bro for the late reply man actually i was outside so i couldn’t got the time to check.
here goes the code.

number,kth=map(int,input().split(" "))
l=list(map(int,input().split(" ")))
l.sort()
counter,index=0,0
finalanswer=number
while index<=number-1:
    if(counter!=0):
        counter-=1
    j=index+1+counter
    while j<number:
        if l[j]-l[index]<=kth:
            counter+=1
            j+=1
        else:
            break
    finalanswer+=counter
    index+=1
print(finalanswer)
1 Like

@karangreat234 bro can you please show some light on how you solved the second question using “Tries” if possible.

your approach gets TLE as its complexity is O(nlogn +n^2), we need O(nlogn + n) approach

@karangreat234 bro can you please expain the solution a bit as i really want to learn its solution as previously i was not that much active in solving the contest problems which i was not able to solve during contest beacuse of which i was not able to grow as CP . :pensive:

1 Like

bro @ssrivastava990 it passed all the test cases man and the complexity in not n^2 .

I was having endsem exam. Thats why no reply… Wait… I’ll explain you in detail :slight_smile:

1 Like