Help in CSES Problem Playlist

help
#1

I am trying to solve the CSES Playlist problem.

https://cses.fi/problemset/task/1141/

I was thinking of a solution with using sets, as given in the code below.
It giving WA for 2 cases. But as this problem comes under Sorting and Searching, I have a feeling as there might be better solutions for this.

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

int main()
{
ll n;
cin >> n;
set<ll> elm;
ll ans = 0, length = 0;
for (ll i = 0; i < n; i++)
{
    int temp;
    cin >> temp;
    int size1 = elm.size();
    elm.insert(temp);
    if (elm.size() > size1)
    {
        length = elm.size();
        ans = max(ans, length);
    }
    else
    {
        elm.clear();
        elm.insert(temp);
    }
}
cout << ans;
return 0;
}

Can someone please help out ?

#2

Your code fails for such input :
10
1 2 3 4 1 5 6 7 8 9
Your answer : 6 (the last six elements)
Correct answer : 9 (the last nine elements)
One way to solve this question is using set and two pointer.

#3

Yeah, I got my mistake. Trying again using two pointers. Thanks for pointing out.

1 Like
#4

@skankhunt_42 I was also stuck at this problem.Applied many approaches but then i landed on geeksforgeeks.

Click Here - Understand the O(n) Algorithm and then write the code you will get AC.

You can check my solution too-My Solution
Hope it Helped!

#5

Thank you !! I was too facing difficulty implementing this.

#6

I used a simple DP approach. Though normal unordered_map will not work but declaring some initial size smoothen things out to run it in 0.1 s

Code 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
int n,ans,arr[N],dp[N];

int main(){
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i)scanf("%d",arr+i);
	unordered_map<int,int> m(1 << 12);
	for(int i = 1; i <= n; ++i){
		if(!m.count(arr[i]))m[arr[i]]= -1;
		dp[i] = max(ans,min(dp[i-1]+1,i-m[arr[i]]));
		m[arr[i]] = i;
	}	
	return printf("%d",*max_element(dp+1,dp+n+1)),0;
}
1 Like
#7

Hey Can you help in my Code, I am getting WA but donā€™t know on which Test Cases?
#include <bits/stdc++.h>
using namespace std;
#define endl ā€˜\nā€™
#define int long long int
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int solve(vector &arr, int n)
{
int ans = -1e18;
deque dq;
unordered_map<int,int> hashMap;
for(int i=0; i<n; i++)
{
if(hashMap[arr[i]]==0)
{
dq.push_back(arr[i]);
hashMap[arr[i]] = 1;
}
else
{
ans = max(ans,(int)dq.size());
while(!dq.empty() and hashMap[arr[i]]!=0)
{
intf = dq.front();
if(f==arr[i])
{
hashMap[arr[i]] = 0;
dq.pop_front();
continue;
}
dq.pop_front();
}
dq.push_back(arr[i]);
hashMap[arr[i]] = 1;
}
}
if(!dq.empty()) ans = max(ans,(int)dq.size());
return ans;
}

int32_t main()
{
fast;
int n; cin >> n;
vector arr(n);
for(int i=0; i<n; i++) cin >> arr[i];
cout << solve(arr,n) << endl;
return 0;
}

#8

Hi,
You can see where you are getting WA on CSES (just Scroll down on the page where you submitted your code).

I was also doing the approach like you did but it failed. Later On, I searched on GeeksForGeeks and i concluded that approach i was applying previously was not able to run on all test cases Correctly.

But GeekForGeeksā€™s Solution is Simple.

You can view the following solutions and you will surely understand it!

My Solution- Click Here
GeeksForGeeks link-Click Here

#9

Hi,
I found where I am getting WA but now I am getting TLE but same logic is passing on Leetcode and GeeksForGeeks Platform, can you help in finding what is its Time Complexity, I think it is O(2n).
#include <bits/stdc++.h>
using namespace std;
#define endl ā€˜\nā€™
#define int long long int
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int32_t main()
{
fast;
int n; cin >> n;
vector arr(n);
for(int i=0; i<n; i++) cin >> arr[i];
int ans = -1e18;
deque dq;
unordered_map<int,int> hashMap;
for(int i=0; i<n; i++)
{
if(hashMap[arr[i]]==0)
{
dq.push_back(arr[i]);
hashMap[arr[i]] = 1;
}
else
{
ans = max(ans,(int)dq.size());
while(!dq.empty() and hashMap[arr[i]]!=0)
{
int f = dq.front();
if(f==arr[i])
{
hashMap[arr[i]] = 0;
dq.pop_front();
continue;
}
dq.pop_front();
hashMap[f] = 0;
}
dq.push_back(arr[i]);
hashMap[arr[i]] = 1;
}
}
if(!dq.empty()) ans = max(ans,(int)dq.size());
cout << ans << endl;
return 0;
}

1 Like
#10

Just change ā€œunordered_mapā€ to ā€œmapā€.
As Worst case complexity of Unordered map is O(n) , Best is O(1)
Mapā€™s Complexity is O(Logn) Throughout.

1 Like
#11

Thank you so much, it worked!!

1 Like
#12

Glad it Helped and surprisingly we both are From Same University!

#13

bro could u tell why unordered map work fast when initialized with size

#15

I donā€™t know exactly but since reason for slow HashMaps are collisions so I think, it is in that direction somewhere.

#16

You can track occurences of each element using a map and then keep two pointers at the ends of distinct segment.

My solution 
#include<bits/stdc++.h>
    using namespace std;
    int main(void){
    	int n,i,j;
    	cin>>n;
    	int a[n];
    	for(i=0;i<n;i++)
    	cin>>a[i];
    	int l=0,r=0,ans=0;
    	map<int,int>mp1;//counting occurence
    	map<int,int>mp2;//setting positions
    	for(i=0;i<n;i++){
    		mp1[a[i]]++;
    		if(mp1[a[i]]==1){
    			mp2[a[i]]=i;
    			r=i;
    		}
    		else{
    			for(j=l;j<=mp2[a[i]];j++)
    			mp1[a[j]]--;
    			l=mp2[a[i]]+1;
    			r=i;
    			mp2[a[i]]=i;
    		}
    		ans=max(ans,r-l+1);
    	}
    	cout<<ans;
    }

PS:Sorry for my English.

#19

why am I getting a TLE using the similar approach as you
https://cses.fi/paste/408cea2327e7ddb2130854/

#20

thatā€™s an amazing tip. Thanks a lot

1 Like