You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFEQ - Editorial

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

This question is marked "community wiki".

asked 09 Feb '15, 19:53

elfus's gravatar image

3★elfus ♦♦
0112527
accept rate: 0%

edited 01 Jun '16, 20:11

admin's gravatar image

0★admin ♦♦
19.8k350498541


why this is not working???/

include<iostream>

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;

}
link

answered 04 Mar '15, 20:29

rishabhr94's gravatar image

2★rishabhr94
1
accept rate: 0%

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

include<iostream>

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

link

answered 17 Dec '15, 20:59

supercool276's gravatar image

2★supercool276
1
accept rate: 0%

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

link

answered 12 Oct '18, 21:56

avatar_7's gravatar image

3★avatar_7
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×3,820
×968
×196
×12

question asked: 09 Feb '15, 19:53

question was seen: 4,668 times

last updated: 12 Oct '18, 21:56