I have a submission with carr[k+1] as well. It gives wrong answer.
Send the new code please
2 Likes
Can u pls help me why this doesnt work?
https://www.codechef.com/viewsolution/29987013
i used set to count unique elements
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lld long long int
int main() {
int t,n,k,m,x,ans=0,d,y,l,b,i,j,z,count;
cin>>t;
while(t--){
cin>>n>>k;
int arr[n];
int carr[k+1]={0};
count=0;
l=-1;
for(i=0;i<n;i++){
cin>>arr[i];
}
for(i=0;i<n;i++){
x=arr[i];
if(carr[x]==0){
count+=1;
}
carr[x]+=1;
while(count>=k){
l+=1;
y=arr[l];
carr[y]-=1;
//cout<<y<<" "<<carr[y]<<endl;
if(carr[y]==0){
count-=1;
}
}
ans=max(ans,i-l);
}
cout<<ans<<endl;
}
return 0;
}@spd_25 you are initializing the ans outside the testcase loop.
initialize the ans=0 inside the while(t–) and your code is correct.
Can someone explain the intuition behind applying the two pointers approach here I don’t actually get it
The first paragraph of explanation 2 explains it, right?
@tmwilliamlin I wanted to ask why there is a condition c[a[R]] in the while loop in your solution (the solution having the two pointers approach) is the condition R<n and c[a[r]] || c2<k has been added wouldn’t be enough to just add R<n and c2<k. correct me if i am wrong?
I have c2<k-1 not c2<k
#include <bits/stdc++.h>
using namespace std;
int a[100001],b[100001];
int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n,k,i,j,flag=0;
cin>>n>>k;
int a[n+1],b[k+1],len=0,mini=0;
bool visited[k+1]={0};
memset(b,-1,4*sizeof(b));
a[0]=0;
for(i=1;i<=n;i++){
cin>>a[i];
visited[a[i]]=1;
}
for(i=1;i<=k;i++){
if(visited[i]==0){
flag=1;
break;}
}
if(flag==1)
cout<<n<<endl;
else{
for(i=1;i<=n;i++){
if(b[a[i]]==-1){
b[a[i]]=i;
len=i-1;}
else{
len=max(len,i-b[a[i]]);
b[a[i]]=i;
}
}
mini=b[1];
for(i=2;i<=k;i++){
mini=min(b[i],mini);
}
// cout<<mini<<" ";
len=max(len,n-mini);
cout<<len<<endl;}
}
return 0;
}
Your code fails in test case like this
1
7 3
1 2 2 3 2 2 1
1 Like
@tmwilliamlin Can you please help me i used a approach where if all the flavors are not in the array directly give the length of the array as the answer else find the gap between the least frequent flavor and the maximum gap becomes the answer…but i am getting wrong answer for my code…can you please tell me the test case where my approach fails…here is the link for my code…CodeChef: Practical coding for everyone
1 Like
#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.