Retr0's blog

By Retr0, history, 3 days ago, In English

Solved

I am getting wrong answer at test case 427. The problem link is here and my solution link is here

#include <bits/stdc++.h>
using namespace std;
 
int main(){
 
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        vector<int> a(n);
 
        map<int,int> mp;
 
        for(int i=0;i<n;i++){
            cin>>a[i];
            mp[a[i]]++;
        } 
 
        bool ok = true;
        for(auto x:a){
            if(mp[x] == 1){
                ok = false;
                break;
            }
        }
        if(ok){
            cout<<0<<endl;
            continue;
        }
 
        int l = -1, r = -1;
        int cnt = 0;
        int len = -INF;
        int ansl = -1, ansr = -1;
        int f = 0;
 
 
        for(int i=0;i<n;i++){
            if(mp[a[i]] == 1 && f == 0){
                l = i;
                f = 1;
            }
            if(mp[a[i]] == 1 && f == 1){
 
                cnt++;
                if(i == n-1){
                    r = i;
                    f = 0;
                    if(len < cnt){
                        len = cnt;
                        ansl = l;
                        ansr = r;
                    }
                } 
            }
            if(mp[a[i]] > 1 && f == 1){
                r = i-1;
                f = 0;
                if(len < cnt){
                    len = cnt;
                    ansl = l;
                    ansr = r;
                }
                // here I forgot to write cnt = 0 after finding probable solution
                // cnt = 0;
            }
        }
        cout<<ansl+1<<" "<<ansr+1<<endl;
 
    }
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Retr0 (previous revision, new revision, compare).

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Your code is not correctly handling the cases where there is a subarray of elements with frequency 1 after the longest subarray which needs to be removed.

Consider the testcase

1

7

1 2 3 4 4 5 6

Your output: 6 7

Answer: 1 3

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much for the test case.

»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

You are not returning "cnt" into 0 after finding such a solution

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Retr0 (previous revision, new revision, compare).