LARGEFAM- EDITORIAL

PROBLEM LINK:

Contest
Practice

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

Can somebody help me out here as I think my program is correct but its showing 2 WAs.
solution

I have trouble understanding what you are trying to do. You are far too focused about zeroes when they are not important. You are bloating your code like hell. Check out the editorials solution, the problem is supposed to be solved in a few lines.

Just for clarification, rewriting your code is a lot easier than sticking to it and trying to fix it.

If you want to fix it, here is a testcase that is wrong for your code.
Input:

2
2
0 2
2
1 2

Your Output:

0
1

Expected Output:

1
1

Edit: Also, try to indent better. Most IDEs have shortcuts for indenting your code if you have trouble with it. It makes structuring your code a lot easier, it makes coding more fun and easier to spot mistakes. Just google “eclipse indent code shortcut” or “visual studio indent code shortcut”. If you don’t use an IDE you have to do it manually and you really should.

Thanks for replying, Now I get it.
Thank u so much.

what should be ans in case of 1 2 2 3 3 4
it should be 2 only not 3 . because in any case max 2 are saying truth not more than that yet your code shows 3 .

1 2 2’ 3 3’ 4
answer: 3

Example:
the child of 1 is 2
the children of 2 are 2’ and 3
the children of 2’ are 3’ and 4

Solution What’s wrong with this solution?

Use long long data type instead of int for sum variable