This question was somewhat similar to maximum length of distinct elements in a string .
Here’s my solution that passed all the test case - CodeChef: Practical coding for everyone
I was also getting wrong answer on test case 7
Things I changed were , I multiplied 1LL with 2 ( please go through the code to see it is multiplied ) and secondly , I made res value to 1e18 .
Yeah, now i understood that we need to check every maxlength distinct subarray.If u are able to comeup with a testcase regarding this.Please forward it to me.
Thank you for the help
My solution is passing all testcase but one. It is not passing 4th tc. Someone explain what is wrong with this code. Can someone give a sample testcase where it fails.
#include <bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0);
typedef long long ll;
int main(){
** FIO;**
** int TC;**
** cin>>TC;**
** while(TC–>0){**
** ll n;**
** cin>>n;**
** vector a(n);**
** for(ll i=0;i<n;i++){**
** cin>>a[i];**
** }**
** if(n == 1){**
** cout<<“0\n”;**
** continue;**
** }**
** vector<pair<ll,ll>> v;**
** unordered_set s;**
** ll st = 0,end = 0;**
** ll i=0,j=0;**
** while(j < n){**
** if(s.find(a[j]) == s.end()){**
** s.insert(a[j]);**
** j++;**
** }**
** else{**
** if((j-1-i) == (end - st)){**
** v.push_back({i, n-j});**
** i = j;**
** j++;**
** s.clear();**
** s.insert(a[i]);**
** }**
** else if((j-1-i) > (end - st)){**
** st = i;**
** end = j-1;**
** v.push_back({st,n-end-1});**
** }**
** else{**
** i = j;**
** j++;**
** s.clear();**
** s.insert(a[i]);**
** }**
** }**
** }**
** if(j-1-i >= end - st){**
** st = i;**
** end = j-1;**
** v.push_back({st,n-end-1});**
** }**
** ll ans = INT_MAX;**
** for(auto p:v){**
** ans = min(ans, 2*(p.first) + p.second);**
** ans = min(ans, p.first + 2*(p.second));**
** }**
** cout<<ans<<endl;**
** }**
** return 0;**
}
input :
1
7
1 1 2 1 1 2 1
output should be : 5
i cannot understand the working of map
But it will only depend on the first subarray with max length and last subarray with max length as all the subarray that occurs in between will never give minimum?
It was really a good problem , CF rating would be 1300-1500 , good editorial
my easy implementation
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template
using ordered_set = tree<T, null_type, less, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = std::less>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long t;
cin>>t;
while(t--){
long long n;
cin>>n;
vector<long long> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
long long l=0;
long long r=0;
map<long long,long long> mp;
long long ans=INT_MAX;
long long cnt=0;
long long left,right;
while(r<n){
while(l<r && mp[v[r]]>=1){
mp[v[l]]--;
l++;
}
if(r-l+1>=cnt){
ans = min(ans,min(2*l+n-r-1,2*(n-r-1)+l));
cnt=r-l+1;
}
mp[v[r]]++;
r++;
}
cout<<ans<<"\n";
}
return 0;
}
see ur code is failing on this test case
1
12
1 1 2 3 4 5 5 1 2 3 4 5
Your code answer : 8
actual answer : 7 (delete index 0 to index 6 )
there u have to calculate answer for all subarray which have same size of maximum distinct element
class Solution:
def __init__(self):
# Ai,j=i+N⋅(j−1)
pass
def solve(self,n,p):
start = 0
end = -1
maxLength = 0
seenSet = set()
ms = []
me = []
while end<n-1:
end+=1
while p[end] in seenSet:
seenSet.remove(p[start])
start+=1
seenSet.add(p[end])
if maxLength<end-start+1:
maxLength = end-start+1
ms = [start]
me = [end]
elif maxLength==end-start+1:
ms.append(start)
me.append(end)
minOp = float("inf")
for i in range(len(ms)):
minOp = min(n-maxLength+min(ms[i],n-me[i]-1),minOp)
print(minOp)
if __name__=="__main__":
t = int(input())
s = Solution()
for _ in range(t):
n = int(input())
arr = list(map(int,input().split()))
s.solve(n,arr)
Consider all sub arrays of max length of sub array with distinct elements.
It is not necessary to consider all the subarray. We just have to consider 1st and last with max length of subarray with distinct elements
https://www.codechef.com/viewsolution/65940771
Here is my code , I am checking all possible subarrays.
The editorialist must provide the code in an explanatory approach and not like they do while submitting in contests. For people who don’t use cpp find it difficult to understand the code and logic through it. They must be more explanatory and simple to understand (no CP shortcuts must be applied). Just a thought 
Code](CodeChef: Practical coding for everyone)
"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int fun(int i, int j, int n)
{
int x = i, y = n - j;
return min((2 * x + y), (x + 2 * y));
}
signed main()
{
int t;
cin >> t;
while (t–)
{
int n;
cin >> n;
vector a(n);
unordered_map<int, int> m;
for (int i = 0; i < n; i++)
cin >> a[i];
int i = 0, j = 0, ans = INT_MAX;
while (i <= j and j < n)
{
if (m[a[j]] == 0)
m[a[j++]]++;
else
{
ans = min(ans, fun(i, j, n));
while (a[i] != a[j])
m[a[i++]]--;
i++;
j++;
}
}
ans = min(ans, fun(i, j, n));
cout << ((ans == INT_MAX) ? 0 : ans) << endl;
}
}
"[
Can you Explain your approach in detail with example.
just what i was looking for…Thank you verymuch
just what i was looking for…Thank you verymuch
a = int(input())
for _ in range(a):
N = int(input())
a = set(input().split())
print(N-len(a))
why is this wrong?