NOTALLFL - Editorial

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

int main()
{
int t;cin>>t;
while(t–)
{
int n,k;cin>>n>>k;

    vector<int>v(n);
    
    for(int i=0;i<n;i++)
    cin>>v[i];
    int cnt,m=0;
    for(int i=0;i<n;i++)
    {
        set<int>s;
        cnt=0;
        while(s.size()<k&&i<n)
        {
            s.insert(v[i]);
            i++;
            cnt++;
        }
        if(s.size()==k){
        cnt--;
        i-=2;}
        
        m = max(m,cnt);
        
    }
    
    cout<<m<<endl;
    
}

}

Why didn’t you just use a pair?

1 Like

#include<bits/stdc++.h>
using namespace std;
#define endl “\n”
#define start ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define test ll t; cin>>t; while(t–)
#define M 1000000007
typedef long long int ll;
int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

start
test
{
	ll n, k, count=0, ans=0;
	cin>> n >> k;
	set<ll> check;
	
	for(ll i=0; i<n; i++)
	{
		ll x;
		cin>>x;
		// to insert unique elements to count their number
		check.insert(x);
		count++;
		// to check if no. of unique elements are greater than k-1
		if( check.size() > (k-1) )
		{
			if( (count-1) > ans )
				ans = (count-1);
			count = 1;
			check.clear();
			check.insert(x);
		}
	}

	if(count > ans)
		ans = count;
	cout<<ans<<endl;
}
return 0;

}

Is anything wrong with this solution i wanted to insert the elements into set to check no. of unique elements and check if they are greater than (k-1). If they are i cleared the set and inserted the current element into set

but this is partially correct.

// simplest
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all© c.begin(),c.end()
#define pb push_back
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int t;
int n, k;
int given[100005];
int lastoccur[100005];
int main() {
scanf("%d", &t);
while (t–) {
memset(lastoccur, 0, sizeof(lastoccur));
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &given[i]);
int ans = 0;

	for (int i = 1; i <= n; i++) {
	
		ans = max(ans, i - lastoccur[given[i]] - 1);
	
		lastoccur[given[i]] = i;
	}

	for (int i = 1; i <= k; i++)
		ans = max(ans, n - lastoccur[i]);

	printf("%d\n", ans);

}
return 0;

}

1 Like

1
16 4
1 1 2 2 1 3 4 2 4 1 2 4 1 2 1 1
ans=10 debugged with this hope it helps anyone incase

2 Likes

Could you please help me out with this code? I am not getting what wrong I have done.

 #include <bits/stdc++.h>
#define ll long long int
#define foro(i,n) for(ll i=0;i<n;i++)
#define forv(i,n) for(ll i=1;i<=n;i++)
using namespace std;

const ll MAXN=100007;
ll a[MAXN];

int main(){
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
foro(i,n){
  cin>>a[i];
}

ll i=0,j=0, cnt=0, ans=0;
unordered_map<ll,ll> mp;
while(j<n && i<=j){
  mp[a[j]]++;
  cnt=mp.size();
   if(cnt==k){
    mp[a[i]]--;
    if(mp[a[i]]==0){
      mp.erase(a[i]);
    }
    i++;
  }
  else{
    j++;
  }
  //cout<<"=="<<i<<" "<<j<<endl;
  ans=max(ans, j-i);
  if(i==j){
    j=i+1;
  }
}
cout<<ans<<endl;
}
}

whats wrong in this please check once.
https://www.codechef.com/viewsolution/33345219

t = int(input())
for _ in range(t):
    n,k = input().split()
    n = int(n)
    k = int(k)
    main= list(map(int,input().split()))
    i = 0
    
    ans = 0
    while(i<n):
        j = i
        temp = []
        count = 0
        maxc = k-1
        while(j<n and maxc>=0):
            if main[j] not in temp:
                maxc-=1
                if(maxc<0):
                    break
                temp.append(main[j])
                if(len(temp)==2):
                    i = j
                
                
                count +=1
                
            else:
                count+=1
            j+=1    
        if(len(temp)<=1):
            i = n
        if(count>ans):
            ans=count
            
    print(ans)

why we did --a[i] in editorial solution 2?

Please test my code and show me where it is getting failed. I am getting partially corrected flag.

def main():
for T in range(int(input())):
    N,K = list(map(int,input().split()))
    segment = dict()
    max_segment_length = 0 
    for i in input().split():
        if segment.get(i) is None:
            if len(segment)+1 < K:
                segment[i]  =  1
            else:
                    # print(segment)
                t = sum(segment.values())
                max_segment_length= max(max_segment_length , t)
                segment = dict()
                segment[i] = 1
        else:
            segment[i] += 1
    # print(segment)
    t = sum(segment.values())
    max_segment_length= max(max_segment_length , t)
    print(max_segment_length)        

                
                
if __name__ == '__main__':
main()

https://www.codechef.com/viewsolution/34713260
can you help me why my code is partially correct any testcase that rule out?
@tmwilliamlin anyone please help me!!

what should be the time complexity for AC ? Can we do this ques using maps ??

Can you please tell me what’s the error?
https://www.codechef.com/viewsolution/36497415

Someone help me understand why my code fails, it’s partially correct for all except task 0 of the first subtask (WA). I follow pretty much the editorial’s solution in my code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define compSpeed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int32_t main(){
	compSpeed;
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		int arr[n];
		for(int i=0;i<n;i++)
			cin>>arr[i];
		int l=0,r=1;
		int cake[n+1] = {0};
		cake[arr[0]] = 1;
		int count=1;
		int ans=0;
		while(1){
		while(r<n && count<k){
			cake[arr[r]]++;
			if(cake[arr[r]] == 1)
				count++;
			if(count<k) ans=max(ans,r-l+1);
			r++;
		}
		if(r==n)
			break;
		while(l<=r && count>=k){
			cake[arr[l]]--;
			if(cake[arr[l]] == 0)
				count--;
			l++;
		}
		}
		cout<<ans<<endl;		
	}
	return 0;
}

Can anyone please tell me why the following code fails?

void solve(int t) {
    test() {
        int n, k;
        cin >> n >> k;
        vector<int> A;
        set<int> s;
        int temp;
        FOR(n) {
            cin >> temp;
            A.push_back(temp);
        }
        int i = 0, j = 0;
        int maxLen = INT_MIN;
        while (j < n) {
            if (s.count(A[j]) == 0) {
                if (s.size() == k-1) {
                    maxLen = max(maxLen, j - i);
                    s.clear();
                    i = j;
                    j--;
                }else{
                    s.insert(A[j]);
                }
            }
            j++;
        }
        maxLen = max(maxLen, j - i);
        cout << maxLen << endl;
    }
}

Can someone help me in finding my mistake @tmwilliamlin
https://www.codechef.com/viewsolution/40191202
its partially correct.
I don’t understand why its not working
I actually implemented this using queue and set instead of pointer

2 Likes

What is wrong with code 50% test cases passed while WA is coming in subtask 2. Please help anyone

import java.io.BufferedWriter;

import java.io.OutputStreamWriter;

import java.util.LinkedHashSet;

import java.util.Scanner;

import java.util.Set;

class Codechef {

public static void main(String[] args) throws java.lang.Exception {

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    Scanner sc = new Scanner(System.in);

    int t = sc.nextInt();

    while (t-- > 0) {

        int n = sc.nextInt();

        int k = sc.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {

            int x = sc.nextInt();

            arr[i] = x;

        }

        Set<Integer> set = new LinkedHashSet<>();

        int l1 = 0, l2 = 0;

        int ans = 0;

        for (l2 = 0; l2 < n; l2++) {

            if (set.size() < k) {

                set.add(arr[l2]);

            }

            if (set.size() == k) {

                ans = Math.max(ans, l2 - l1);

                set.remove(arr[l1]);

                if (set.size() == 1) {

                    l1 = l2;

                } else {

                    ++l1;

                }

            }

        }

        ans = Math.max(ans, l2 - l1);

        bw.write(ans + "\n");

    }

    sc.close();

    bw.close();

}

}

indent preformatted text by 4 spaces
`#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    unordered_map<int,int> mp;
    if(n<k)
    {
        cout<<n<<"\n";
    }
    else if(n>=k)
    {
        for(int i=0;i<k-1;i++)
        {
            mp[a[i]]++;
        }
        int cnt=0;
        for(int i=1;i<=k;i++)
        {
            if(mp[i]==0)
            {
                cnt++;
            }
        }
        int l=0,r=k-2,sz=k-1;
        while(r<n)
        {
            if(r+1<n)
            {
                if(mp[a[r+1]]>0)
                {
                    r++;
                    mp[a[r]]++;
                    sz=max(sz,r-l+1);
                }
                else if(mp[a[r+1]]==0)
                {
                    if(cnt>1)
                    {
                        r++;
                        mp[a[r]]++;
                        cnt--;
                        sz=max(sz,r-l+1);
                    }
                    else if(cnt==1)
                    {
                        while(cnt==1)
                        {
                            if(mp[a[l]]==1)
                            {
                                cnt++;
                            }
                            mp[a[l]]--;
                            l++;
                        }
                        r++;
                        mp[a[r]]++;
                        cnt--;
                        sz=max(sz,r-l+1);
                    }
                }
            }
            else
            {
                break;
            }
        }
        cout<<sz<<"\n";
    }
}
}`