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

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

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)?) If you can’t think of one, wait for the Editorial

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()