MONKS - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Tester: Jeevan Jyot Singh, Nishank Suresh
Editorialist: Yash Kulkarni

DIFFICULTY:

1776

PREREQUISITES:

PROBLEM:

There is a town with N people and initially, the i^{th} person has A_i coins. However, some people of the town decide to become monks. If the i^{th} person becomes a monk, then:

  • He leaves the town thereby reducing the number of people in the town by 1.
  • He distributes X (0 \le X \le A_i) coins to the remaining people of the town (not necessarily equally). Note that each monk can freely choose his value of X, and different monks may choose different values of X.
  • He takes the remaining A_i - X coins with him.

For example, initially, if A = [1, 3, 4, 5] and 4^{th} person decides to become a monk then he can leave the town and can give 2 coins to the 1^{st} person, 1 coin to the 2^{nd} person, no coins to the 3^{rd} person and take 2 coins along with him while going. Now A becomes [3, 4, 4].

Determine the minimum number of people who have to become monks, so that in the end, everyone remaining in the town has an equal number of coins.

EXPLANATION:

Let B be the set of people who become monks and C be the set of people who do not become monks. For all the people in C to have an equal number of coins, it is sufficient and optimal to distribute coins from the people in B to the people in C so that all the people in C have as much coins as the maximum coins held initially by any person in C.

Let Max_C be the maximum coins held initially by any person in C, Size_C be the size of C, Sum_B be the sum of the coins held initially by all the people in B, and Sum_C be the sum of the coins held initially by all people in C. It is clear that we have Sum_B coins to distribute among people in C and the minimum number of coins required so that all the people in C have Max_C coins is Max_C \times Size_C - Sum_C. So, this selection of B and C is possible if Sum_B \geq Max_C \times Size_C - Sum_C.

C is characterized by Max_C so we can go over all possible C by iterating over each A[i] = Max_C. This means that all elements of A having values higher that A[i] will fall into B. This iteration is very easy if A is sorted because Size_C can be found easily using the index i, Sum_C is the prefix sum till index i, Sum_B is suffix sum for index i+1, and Max_C is A[i].

We will pick the split (of B and C) which is valid (satisfies the condition) and has minimum Size_B or maximum Size_C as required in the question.

TIME COMPLEXITY:

O(N log(N)) for each test case.

SOLUTION:

Setter's solution
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5; 

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

int sumN = 0;

void solve()
{
    int n = readIntLn(1, 1e5);
    sumN += n;
    vector<int> a = readVectorInt(n, 1, 1e9);
    sort(a.begin(), a.end());
    vector<int> pref = a;
    for(int i = 1; i < n; i++)
        pref[i] += pref[i - 1];
    for(int i = n - 1; i >= 0; i--)
    {
        int S = pref.back() - pref[i];
        int P = pref[i];
        if((i + 1) * a[i] - P <= S)
        {
            cout << n - (i + 1) << endl;
            return;
        }
    }
    assert(false);
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 1e5);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    assert(sumN <= 2e5);
    readEOF();
    return 0;
}
Editorialist's Solution
using namespace std;
#define ll long long

int main() {
	ll T;
	cin >> T;
	while(T--){
	    ll n;
	    cin >> n;
	    vector<ll>a(n);
	    ll sum=0;
	    for(ll i=0;i<n;i++){
	        cin >> a[i];
	        sum+=a[i];
	    }
	    sort(a.begin(),a.end());
	    if(a[n-1]==a[0]){
	        cout << 0 << endl;
	        continue;
	    }
	    ll curr=0;
	    ll ans=n;
	    for(ll i=0;i<n;i++){
	        curr+=a[i];
	        ll x=sum-curr;
	        if(x>=a[i]*(i+1)-curr)ans=min(ans,n-i-1);
	    }
	    cout << ans << endl;
	}
	return 0;
}
1 Like

[Solution: 70106235 | CodeChef]
can anyone tell why i am getting TLE ?

I have a doubt according to the question constarint are 1≤T≤10^5 , 1≤N≤10^5 so for the worst case if we sort the array timecomplexity will be( t * nlogn) which is equal to 10^5 * 10^5 * log(10^5) which is equal to 10^11 which is not acceptable for 1 sec. So why we are sorting here. its not possible. right?

2 Likes

It is written in the constrains: “Sum of N over all test cases does not exceed 2.10^5”
so it will be just 2.10^5*log(10^5)

Your code runs in O(N^2) where N can be as large as 10^5, which means your code has to run 10^10 operations in worst case, which leads to TLE.

1 Like

Can any one please help me why I am getting TLE on sub-task 2
I am unable to find my mistake.
Solution: 70231254 | CodeChef
Thanks in advance.

Your logic is correct, but when using Java, you have to be aware that input reading and output writing can cause TLE for large inputs/outputs. Don’t use the standard Scanner and don’t use System.out.println. Here is a minimal fix:

https://www.codechef.com/viewsolution/70235459
you can read a bit more about Java IO here: How to read input in Java — tutorial - Codeforces
you may also want to check out array sorting, because you used an O(n²) algorithm (quicksort) in your code: How to sort arrays in Java and avoid TLE - Codeforces

Thanks a lot sir
I had fixed the code according to the given instructions in your reply sir, which has fixed the error of getting TLE sir.
Thanks a lot for sharing resources sir.

1 Like

We can solve it greedily. What I have done is that I initially supposed all guys to be monks and then greedily iterated over the sorted array and check if monks can be reduced or not.
Let suppose our array was [2,5,6,10,8,3] so after sorting it becomes [2,3,5,6,8,10]. Now let suppose all members decided to be monks so monks = 6. So we have coins = total sum of all elements of array which is 34. let say our person 1 dont want to be monk., then our coins become 32 and we have person 1 as a town member but theres no need to give him coins as theres only one member in town so our monks now reduce to 5. Now we again check for person 2. If he dont wanna be a monk then we will have coins = 32 - 3 = 29 which we can distribute. and our town people now become [2,3] so we know all those people in town will have coins equal to the maximum coins that is 3. so 2 members will have 3 coins each and we have currently (2+3) coins = 5. so required coins = (2 * 3) - (2 + 3) = 1, obviously we can take 1 coin from those 29 coins and give to person 1, so that all have 3 coins each which reduces the number of monks to 4. Similarly we go to person 3 and check if he can be member of town. so now members =[2,3,5] and coins = 29 - 5 = 24. We want to make all person coins = 5. IN order to do it we require (5 * 3 ) - (2 + 3 + 5) = 5 coins. we again can take 5 coins from 24 coins and give distribute it among 3persons so that all have 5 coins each. now our monk becomes 3. same way we check for all the persons and for any index we get required coins<coins offered by monks that time we get the minimum number of monks.
Screenshot (106)