Why do i get TLE in subtask 2 of NOTALLFL LunchTime problem 2

link to the question: https://www.codechef.com/LTIME81B/problems/NOTALLFL
my code shows TLE for the last case…

#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int T;
	cin >> T;
	while(T--)
	{
		int n,k,i,j,z;
		cin >> n >> k;
		vector<int> A(n),flv(k+1);
		for(i=0;i<k+1;i++)
			flv[i]=0;
		for(i=0;i<n;i++)
			cin >> A[i];

		int flv_count,count,max=0;
		for(i=0;i<n;i++)
		{
			flv_count=0,count=0;
			for(j=i;j<n;j++)
			{
				if((flv_count==k-1 && flv[A[j]]==0) || (count+n-j)<max)
						break;
				else
				{
					if(flv[A[j]]==0){
						flv[A[j]]=1;
						flv_count++;
					}
					count++;
				}
			}
			if(count>max)
				max=count;
			if((n-i)<max)
				break;
			for(z=0;z<k+1;z++)
				flv[z]=0;
		}
		cout << max << endl;
	}
	return 0;
}

Consider the testcase where N=100000, K=50000, and the first K elements of A are 1,2, ... , K, and so are the last K elements of A.

Edit:

i.e. this :slight_smile:

3 Likes

can you suggest some improvements to my code to solve the issue?

Use an algorithm that is not O(N^2) (or is it O(N \times K)?) :slight_smile: If you can’t think of one, wait for the Editorial :slight_smile:

3 Likes


Editorial.

2 Likes

thanks

1 Like

I have code this problem. I am also getting same partial correct solution. Can any one help with this solution?

# cook your dish here

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 int(i)<=K :
                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()