BUDGET25 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Testers: apoorv_me, tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are N sectors, the i-th has budget A_i.
It’s possible to transfer some budget from one sector, but only if the first sector remains with a budget of at least X after the transfer.
Find the maximum number of sectors that can have a budget of at least X after some transfers.

EXPLANATION:

Let’s call a sector good if A_i \geq X, and bad otherwise.

Each good sector gives us some amount of budget that can be transferred to a bad sector.
Since we aren’t allowed to go below X, we can transfer (A_i - X) to other sectors.

Let S denote the sum of (A_i - X) across all good sectors i.
This extra S can then be distributed to bad sectors to (hopefully) make them reach X themselves.

Clearly, it’s best to first distribute to whichever sectors are already closest to reaching X - that is, it’s optimal to distribute to bad sectors in descending value of their A_i values.

This gives us the following algorithm:

  • Compute S as the sum of (A_i - X) across all i such that A_i \geq X.
  • Then, consider all i such that A_i \lt X.
    Iterate over them in descending order of A_i, and if S \geq X - A_i, set A_i to X and reduce S by (X - A_i).

Iterating over values in descending order is easily done by simply sorting them first.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ans, extra = 0, 0
    for y in reversed(a):
        if y >= x:
            ans += 1
            extra += y - x
        else:
            if extra >= x - y:
                extra -= x - y
                ans += 1
    print(ans)
2 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int test_cases;
    cin>>test_cases;
    for(int i = test_cases ; i >= 1 ; i--){
        int n, min_budget, extra_available = 0;
        cin>>n>>min_budget;
        vector<int> amounts(n), required;
        for(int j = 0 ; j < n ; j++){
            cin>>amounts[j];
        }
        for(int j = 0 ; j < n ; j++){
            if(amounts[j] < min_budget)
                required.push_back(min_budget - amounts[j]);
            else if(amounts[j] > min_budget)
                extra_available += amounts[j] - min_budget;
        }
        if(required.empty()){
            cout<<n<<endl;
            continue;
        }
        if(required.size() == n){
            cout<<0<<endl;
            continue;
        }
        sort(required.begin(), required.end());
        int j = 0, solved = 0;
        for(j = 0 ; j < required.size() ; j++){
            if(extra_available < required[j])
                break;
            extra_available -= required[j];
            solved++;
        }
        cout<<n - (required.size() - solved)<<endl;
    }
}

Could someone find any bug in my code? It passed only 3/5 test cases.

3

Just make sure to have long long data type for extra_available…i too was facing the same issue…but got it resolved by changing the data-type