Largest Family CodeChef Solution


Largest Family CodeChef Solution

Largest Family CodeChef Solution

A certain parallel universe has exactly NN people living in it.

The ii-th of these NN people claims that they are the parent of exactly AiAi of these NN people.

However, some of these people might be lying ‚ÄĒ the¬†ii-th person may be either telling the truth (in which case they have exactly¬†AiAi¬†children) or lying (in which case they can have any number of children).

It is known that each person has¬†at most one¬†parent. Further, as one would expect, it is¬†not allowed¬†for a person’s child to also be their ancestor.

What is the maximum possible number of truth-tellers in this universe?

Input Format

  • The first line of input will contain a single integer¬†TT, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains a single integer¬†NN, the number of people.
    • The second line of each test case contains¬†NN¬†space-separated integers¬†A1,A2,‚Ķ,ANA1,A2,‚Ķ,AN.

Output Format

For each test case, output on a new line the maximum number of people that can be telling the truth.

Largest Family CodeChef Solution


  • 1‚ȧT‚ȧ4‚čÖ1041‚ȧT‚ȧ4‚čÖ104
  • 1‚ȧN‚ȧ3‚čÖ1051‚ȧN‚ȧ3‚čÖ105
  • 0‚ȧAi<N0‚ȧAi<N
  • The sum of¬†NN¬†across all test cases won’t exceed¬†3‚čÖ1053‚čÖ105.


  • Subtask 1 (20 points):
    • 1‚ȧT‚ȧ51‚ȧT‚ȧ5
    • 1‚ȧN‚ȧ201‚ȧN‚ȧ20
  • Subtask 2 (80 points):
    • No further constraints.

Sample Input 1 

1 0
1 1
2 0 1
2 3 1 2 3

Sample Output 1 



Largest Family CodeChef Solution

Test case 11: Both people can be telling the truth, with the first person being the parent of the second.

Test case¬†22:¬†If both people were telling the truth, they would be each others’ parents ‚ÄĒ and that is not allowed. Hence, at most one of them can be telling the truth.

Test case¬†33:¬†The first and third people cannot be telling the truth at the same time. However, it is possible for the first and second people to be truthful ‚ÄĒ person¬†11¬†can be the parent of person¬†22¬†and person¬†33. Hence, the answer is¬†22.

Test case¬†44:¬†There are several ways to pick¬†22¬†people to be telling the truth ‚ÄĒ for example,

  • The parent of person¬†22¬†and person¬†33¬†is person¬†11
  • The parent of person¬†11¬†and person¬†55¬†is person¬†44

in which case persons number 11 and 44 would be telling the truth.

However, it can be shown that it is impossible for any three of them to be simultaneously telling the truth.

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

Related Posts

Leave a Reply

Your email address will not be published.