#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.
// 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 ??
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";
}
}
}`