NOTALLFL - Problem Partially Correct

CodeChef-DSA-learners dsa-learning-session
,
1

Problem
My solution

My approach:
If total elements is less than total no. of flavors or total unique elements are less than total no. of flavors. → Max subsequence without one element = total no. of elements

If not:
Max subsequence will always have atleast one less unique elements, i.e. sum less than than A.P of total number of flavors. We can use set to keep track of unique elements, but that would be O(kn) approach since for every new sequence we will have to clear the set. So i have used map and another variable to keep track of new sequence. Whenever a sequence ends we know the sum will have become equal to AP of k flavors. So to reset the map I have used seqno which is the another variable. And on every iteration I update the length of the longest subsequence if it less than the maxsum.

I have tried many test cases but not sure where I am going wrong. Any help will be appreciated. If my approach/code is not clear, let me know I’ll try to explain it better.

Thanks

2

You have to find largest contiguous subsegment where no of types is less than k. I am not getting why are you using maxsum and how AP ?

You can see my sol

Code 
#include <bits/stdc++.h>
using namespace std;
int arr[1000001];
#define lld long long int 
int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        unordered_map <int,int> mp;
        for(int i=0;i<n;i++)
        cin>>arr[i];
        unordered_set <int> s;
        int start=0,res=0;
        for(int i=0;i<n;i++)
        {
            s.insert(arr[i]);
            mp[arr[i]]++;
            if(s.size()==k)
            {
                while(s.size()==k)
                {
                    mp[arr[start]]--;
                    if(mp[arr[start]]==0)
                    s.erase(s.find(arr[start]));
                    start++;
                }
            }
            res=max(res,i-start+1);
        }
        cout<<res<<"\n";
        
    }
}
3

@Sebastian
The sum of all flavors is (k(k+1)/2) AP sum right. So the largest contiguous subsegment will always have sum less than this(only considering the unique elements), since it will be missing atleast one element.

4

1
6 3
2 2 3 1 1 1

1 Like
5

Oh thanks