PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Tushar Gupta
Tester: Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY:
Cakewalk
PREREQUISITES:
Greedy
PROBLEM:
You are given an array A with N integers, where i-th element A_i represents the flavor type of the i-th chocolate. Sebrina wants to eat as many different types of chocolates as possible but she also has to save at least X chocolates for her little brother.
Your task is to find the number of unique chocolates Sebrina can eat.
EXPLANATION:
Suppose the number of unique chocolates that Sebrina initially has is S. She will save X chocolates for his brother, hence the number of chocolates that Sebrina will eat is N-X, say this value Y. Now, we can use a greedy approach to find out the number of unique chocolates that Sebrina can have. There can be two cases possible:
Case 1: S \ge Y
Since the number of unique chocolates that Sebrina has is greater (or equal) to the number of chocolates that she will eat. Hence she will always eat a different flavor of chocolate. Hence she will eat Y unique chocolates as the maximum chocolate that she can eat is Y.
Case 2: S < Y
As the number of unique chocolates that Sebrina has is less than the number of chocolates that she will eat. Hence, in this case, it is always possible to eat all the unique chocolates that she has. Therefore, she can eat S unique chocolates.
Finally, we, output the answer accordingly.
TIME COMPLEXITY:
O(N*log(N) per test case
SOLUTIONS:
Setter
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while( t-- ){
int n, x; cin>> n >> x ;
int df[n];
for( auto &i : df ) cin >> i ;
sort( df , df+n );
int total_unique = 0 ;
int total_giveaway = 0;
int last_type = df[0];
int cur_tot = 0 ;
for( int i = 0 ; i < n; ++i ){
if( last_type == df[i] ) cur_tot++;
else{
total_unique++;
total_giveaway += cur_tot-1;
cur_tot = 1;
}
last_type = df[i];
}
total_unique++;
total_giveaway += cur_tot-1;
if( total_giveaway >=x ) cout << total_unique;
else cout << total_unique - ( x- total_giveaway ) ;
cout << '\n';
}
}
Tester
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
void solve() {
int n, x;
cin >> n >> x;
vi a(n);
rep(i, 0, n) cin >> a[i];
sort(all(a));
a.erase(unique(all(a)), a.end());
cout << min(sz(a), n - x) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n,x;
cin>>n>>x;
set<int> s1;
for(int i=0;i<n;i++)
{
int temp;
cin>>temp;
s1.insert(temp);
}
int ans=(int)s1.size();
ans=min(ans,n-x);
cout<<ans<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}