PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Prakhar Goyal
Tester: Abhinav Sharma, Lavish Gupta
Editorialist: Devendra Singh
DIFFICULTY:
1877
PREREQUISITES:
Map data structure, Two pointers approach
PROBLEM:
You are given an array A of N integers. You must perform some (possibly zero) operations to make the elements of A distinct.
In one operation, you can either:
- Remove one element from the beginning of the array A and append any positive integer to the end.
- Or remove one element from the end of the array A and prepend any positive integer to the beginning.
Find the minimum number of operations required to make all the elements of the array distinct.
EXPLANATION:
It is trivial that after some operations the final array contains a prefix of distinct elements inserted into A followed by a subarray of A which contains distinct elements or a subarray of A which contains distinct elements is followed by a suffix of distinct elements inserted into A. For each index i where 1\leq i \leq N, we assume the subarray present in the final answer starts at this index and to decrease the number of operations we need the maximum length of such subarray for each index. For each index i where 1\leq i \leq N, we need to find maximum index j where i\leq j such that the subarray A[i,j] contains distinct elements. This can be done using two pointers approach in O(Nlog(N)).
Observation
Let the optimal answer contain the subarray A[i,j],Let R denote the number of elements in the suffix of the array A starting from j+1 i.e A[j+1,N] and L denote the number of elements in the prefix of array A ending at i-1. Let L<=R, then the answer cannot be less than 2\cdot L+R. This is because until all elements till index i-1 are deleted by performing operation of type 1, performing an operation of type 2 only increases the total number of operations. Thus it is optimal to have all similar operations together. Similarly the case when R<=L can be analyzed.
The minimum number of operations required to delete all numbers upto index i-1 and from j+1 to N is min(2\cdot (i-1)+N-j,i-1+2\cdot (N-j)). Minimum of this value over all indices i is the answer.
TIME COMPLEXITY:
O(Nlog(N)) for each test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FOR(i, x, n) for (ll i = x; i < n; i++)
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1;
cin>>t;
while (t--)
{
ll n , k;
cin>>n;
vector<ll> A(n);
FOR(i,0 ,n)
cin>>A[i];
unordered_set<ll> st;
ll ind = 0;
ll ans =LLONG_MAX;
FOR(i, 0 ,n)
{
if(st.count(A[i])==1)
{
ll r = n-i;
ll l =ind;
// cout<<i<<"\n";
ans = min(ans , 2*min(l , r) + max(l , r));
FOR(j , ind , n)
{
if(A[i]==A[j])
{
ind = j+1;
break;
}
else
st.erase(A[j]);
}
st.insert(A[i]);
}
else
{
st.insert(A[i]);
}
}
ans = min(ind , ans);
cout<<ans<<endl;
}
}
Editorialist's solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n;
cin >> n;
vll v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
int ans = 1e9;
map<int, int> mp;
int r = 0;
for (int l = 0; l < n; l++)
{
while (r < n && !mp[v[r]])
{
mp[v[r]]++;
r++;
}
ans = min(ans, l + 2 * (n - r));
ans = min(ans, 2 * l + n - r);
mp[v[l]]--;
}
cout << ans << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}