BUDGET25 - Editorial

Author: notsoloud
Testers: apoorv_me, tabr
Editorialist: iceknight1093

TBD

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)


#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.

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