CM164364 - Editorial

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;
}

1 Like

can any one tell what is wrong with my sol
https://www.codechef.com/viewsolution/45220942

Please explain the example data:
INPUT:
3
2 1
1 2
4 2
1 1 1 1
5 3
50 50 50 100 100
OUTPUT:
1
1
2

Explanation of test case 1 is already given on the problem page.

  • For 2nd test case:
    There are 4 chocolates available. All of them are of the same type i.e., type 1.
    She should reserve x = 2 chocolates for her brother. After reserving 2 chocolates of type 1, she’s left with 2 of the same type. Since the number of unique flavours of chocolates she can eat is 1, the answer for this test case is 1.

  • For 3rd test case:
    There are 5 chocolates available. 3 of them are of one flavour while the rest 2 are of another flavour.
    Now she has to reserve 3 chocolates for her brother. If she reserves 3 chocolates of flavour type 50, she will be left with two chocolates of type 100. The number of unique flavours she is left with is 1.
    But there is a better choice - she reserves two chocolates of type 50 and 1 chocolate of type 100. Now, she’s left with one chocolate of type 50 and one of type 100. Since the number of unique chocolates she’s left with is maximum in 2nd choice, the answer is 2.

1 Like

Thank you! I thought that each value A[i] was the quantity of each type.

#include

using namespace std;

int main() {
int j,t,n,x;
cin>>t;
int c[t];

for(int i=0;i<t;i++)
{
cin>>n>>x;
int ten=1,a[n];
for(j=0;j<n;j++)
cin>>a[j];
for(j=1;j<n;j++)
{
for(int k=0;k<j;k++)
if(a[j]!=a[k])
ten++;
}
n=n-x;
if(n>ten)
c[i]=ten;
else
c[i]=n;
}
for(j=0;j<t;j++)
cout<<c[j]<<endl;

return 0;
}

//why isn’t this correct?

can anyone tell what’s wrong with my code?
https://www.codechef.com/viewsolution/45257669

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
int t;
cin >> t;
while (t–)
{
int n, x, A[n];

    map<int, int> mp;

    cin >> n >> x;

    for (int i = 0; i < n; i++)
    {
        cin >> A[i];

        mp[A[i]]++;
    }

    if (n == x)
        cout << "0" << endl;

    else
    {
        int ans = n - x;
        if (mp.size() < ans)
        {
            cout << mp.size() << endl;
        }

        else if (mp.size() >= ans)
        {
            cout << ans << endl;
        }
    }
}

}

What’s wrong with this code? It is giving runtime error on codechef.
But when i don’t take input in the array as A[i] but i directly take input in the map the code works

#include<bits/stdc++.h>

const int mod = 1e9+7;

using namespace std;

int32_t main()
{
int n,m,q,node,edge,x,y,i,j,count=0,temp,flag1=0,flag2=0;

cin>>q;

while(q--)
{
    cin>>n>>temp;
    
    int arr[n];
    
    for(i=0;i<n;i++)
        cin>>arr[i];
        
    set<int>S;
    
    for(auto u : arr)
        S.insert(u);
    
    x = S.size(); 
    cout<<min(x,n-temp);

// If the number of chocolates, that are different are
// are large in number(in a large variety) then she can eat at max (n-temp) chocolates,
// becoz she has to save ‘temp’ chocolates for brother
// otherwise if they are few different chocolates, but quantity of each is large
// then at max she can have x chocolates (counting all different chocolates).
if(q)
cout<<"\n"
}

int do_not_hack;

return 0;

}

Simple if We Use Map
just insert and count the chocolate-1 and then just check it

#include<bits/stdc++.h>
using namespace std;
#define fo(i,n) for( int i=0;i<n;i++)
#define int long long int
#define deb(x) cout << #x << “=” << x << endl
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
typedef vector vi;
typedef pair<int, int> pii;

void solve() {
int n,t;
cin>>n>>t;
map<int ,int> m;
map<int ,int>::iterator itr;
for(int i=0;i<n;i++)
{
int t;
cin>>t;
itr=m.find(t);
if(itr!=m.end())
itr->ss++;
else
m.insert(pair<int,int>(t,1));
}
int c=0;
int sum=0;
for(itr=m.begin();itr!=m.end();++itr)
sum=sum+(itr->ss)-1;
if(sum>=t)
cout<<m.size()<<endl;
else
{
int x=m.size()-t+sum;
cout<<x<<endl;
}

}

int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
int t = 1;
cin >> t;
while(t–) {
solve();
}

return 0;

}

Use a map …it makes it easier

1st line test case
2nd line ->no of chocolates ,no of chocolates for her brother;
the different kinds of flavors;
just out put min(no of diff flavours,no of chocolates-no of chocolates for her brother)
hope u got it