PROBLEM LINK:
Setter: iceknight1093
Testers: gamegame
Editorialist: aryanag_adm
DIFFICULTY:
1532
PREREQUISITES:
Sorting, Greedy
PROBLEM:
You are given an array A of length N consisting of positive integers. The array is meant to represent the configuration of a forest of rooted trees with N nodes, where A_i is the number of children that node i has.
A may not correspond to a valid configuration of a forest; therefore, we can change some elements of A. Find the maximum number of elements that can remain unchanged, so that A corresponds to a forest with N nodes.
EXPLANATION:
Claim: A corresponds to a tree if and only if \sum_{i=1}^N A_i = N-1
Proof:
If A does correspond to a tree, then \sum_{i=1}^N A_i = number of edges in the tree = N-1.
Now, assume the sum is N-1. If N = 1 then A clearly corresponds to the unique tree with 1 node. Now, for N > 1, since the sum of A is N-1, there must exist at least one i with A_i = 0. Delete A_i from A. Now A has length N-1 and sum N-1. Therefore, there must exist a j with A_j > 0. Set A_j = A_j - 1. Now, A has length N-1 and sum N-2. Therefore, by induction, A corresponds to some tree with N-1 nodes. We simply add A_i as a child of A_j in this tree. This is now a tree corresponding to the original A.
This completes the proof.
Now, using the above claim, it’s easy to see that A corresponds to a forest if and only if \sum_{i=1}^N \leq N-1.
Therefore, if the sum of elements in A is already \leq N-1, the entire array can remain unchanged. If the sum of elements is \geq N, then we want to keep the maximal number of elements whose sum is \leq N-1, and we can just change the remaining elements to 0. The obvious greedy approach where we keep changing the maximum element of A works.
TIME COMPLEXITY:
Time complexity is O(N \cdot log(N)).
SOLUTION:
Editorialist's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
#define int long long
#define double long double
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
signed main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
priority_queue<int> pq;
int sum = 0;
for(int i = 0;i<n;i++){
cin>>a[i];
pq.push(a[i]);
sum += a[i];
}
int ans = n;
while(sum >= n){
ans--;
sum -= pq.top();
pq.pop();
}
cout<<ans<<endl;
}
}