CHEFEQ - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Abhra Dasgupta
Tester: Pushkar Mishra
Editorialist: Florin Chirica

PROBLEM

Let’s formalize the problem. Suppose you’re given an array read from the input.

Operation #1: Pick some coins from any pile and put them back in Chef’s coin box.

This means we can decrease the number of coins from any pile.

Operation #2: Pick some coins from the Chef’s coin box and put them on any one pile.

This means we can increase the number of coins from any pile.

Observations #1 and #2 combined tell us we can change the number of conins from any pile to what number we want. Our goal is to have the same value in each pile.

QUICK EXPLANATION

The trick is to find the most frequent value and make all array equal to that value.

EXPLANATION

Picking the most frequent value

So you get an array and you can change what element you want. What’s the minimal number of changes in order to get all elements equal?

Denote x as the value in the array after we finish all operations. Obviously, x must be a value from the initial array. A brute force algorithm could be taking 1st element, 2nd element, …, nth element and assume it is x. Then, calculate the cost and pick the minimal cost. However, this takes O(n ^ 2), which is too much for get full score.

Let’s try something else. After we pick an x, the cost is equal to number of elements that have different value from x. This cost is also n - number of elements that have the same value with x. Since n is constant, we need to minimize expression: (-(number of elements that have the same value with x)), or maximize the expression (number of elements that have same value with x). (We got this considering that if -a is minimized, then a will be maximized).

So maximizing number of elements that have the same value with x can be done by finding the most frequent element from the array.

Finding the most frequent element of the array

We’ll present two ways to get it:

First way is based on the small values for A[i] elements. We can keep an array count[x] = how many times does value x appear in the array. Then, we can iterate elements of count from 0 to 10^5 (the upper limit for A[i]) and store the maximum.

The second way is based on the fact that elements having the same value form a contiguous subsequence in the sorted array. So we sort our array and divide it in “blocks” having the same value. An element x will appear in exactly one block of elements having the same value. This approach can be used to solve the problem even if we’re not given A[i] <= 10^5 restriction.

Depending on how you implement it, the complexity is either O(n + maximumValue) or O(n * log(n)).

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution

Setter’s solution

2

why this is not working???/

#include
using namespace std;
int main()
{ int t,l;

	cin>>t;
	
	for(int i=1;i<=t;i++)
	{	int c=0;
		int max=1;
		int count=0;
		int num;
		cin>>num;
		int piles[100001]={0};
		
		for(int i=0;i<num;i++)
		{
			cin>>piles[i];
		}
	
	for(int i=0;i<num;i++)
	{
		for(int j=i;j<num;j++)
	{ 
		if(piles[i]==piles[j])
			count=count+1;
	}
		if(count>max)
		{
			max=count;
			l=piles[i];
		}
	}
		if(num==1)
		{
		cout<<c;
		}
	
	else if(count==1)
	{
		for(int i=1;i<num;i++)
		{
			if(piles[0]!=piles[i])
				c++;
		} 
	
		cout<<c;
		cout<<endl;
	}
		else
		{
			for(int i=0;i<num;i++)
		{
			if(l!=piles[i])
				c++;
		} 
	
		cout<<c;
		cout<<endl;
		}
	}
		return 0;

}
3

i think we can increase memory complexity by taking an extra array so time complexity reduces to O(n)

#include
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int flag[100005] = {0};
int max = 0;
for(int i=0;i<n;i++){
int x;
cin>>x;
flag[x]++;
if(flag[x]>max){
max = flag[x];
}
}
cout<<n-max<<endl;
}
return 0;
}

4

//Very Easy By Using Map. Only Find Most Frequent Number And Subtract It From ‘n’ (n=Number Of Element).
#include <bits/stdc++.h>
using namespace std;
#define ll long long

#define GIO ios_base::sync_with_stdio(0);cin.tie(0);
int main()
{ GIO;
ll T;
cin>>T;
while(T–)
{ ll n;
cin>>n;
map<int,int> m;
for(ll i=0;i<n;i++)
{ ll a;
cin>>a;
m[a]++;
}
ll mi=INT_MIN;
ll c=0;
for(auto it=m.begin();it!=m.end();it++)
{if(it->second>mi)
{mi=it->second;
c++;
}
}
cout<<n-mi<<"\n";
}
return 0;
}