Problem Link
Author: Praveen Dhinwa
Tester: Pawel Kacprzak and Misha Chorniy
Editorialist: Bhuvnesh Jain
Difficulty
EASY
Prerequisites
Greedy & Constructive Algorithms
Problem
You are given an array a, where a[i] denotes the number of subjects i has as a pre-requisite. Also it is given that a[i] < i for 1 <= i <= n. You need to arrange the dependencies among subjects such that the number of subjects which are not pre-requisite of any other subject is maximized in number. Also, a pre-requisite for a course should be of lower difficulty than itself.
Explanation
The solution to the problem is simply n - max(a), where max(a) denotes the maximum element in the array. To see why the above claim holds true, we just use the fact that a given subject can act as the pre-requisite for more than one subject too. So, we apply greedy strategy here and find the subject which has most subjects as its pre-requisite. So, we need atleast these many subjects which cannot count to our final answer. Now, we claim that there is always a way to select these subjects only and form our answer such that remaining subject have no dependencies.
Just select the subject with the maximum number of dependencies. If multiple such subjects exist, select the one with the lowest difficulty. Then select subjects with least difficulty (will be the starting subjects only) and have difficulty less than the above-selected subject. We claim that these subject can act as pre-requisite for all the courses. These subjects can definitely act as pre-requisite for all courses that have difficulty greater than them. Now, if some subjects among the selected ones also have dependencies, then subjects of lower difficulty as also present and can act as pre-requisite for these too. (as there is no limit on the subject as to how many subjects have it as a pre-requisite). Also, above selection is possible as it is given that a[i] < i.
Let us see this through an example as well. Let the array a be :
a = \{0, 1, 0, 2, 3, 1, 3, 2\}
From the above argument, we select the subject 5, first as it has the maximum number of dependencies (subject 7 is not selected as it is of higher difficulty). Now the claim is that the first 3 subject can act as pre-requisite for all the subjects. This is because subject 1 can act as pre-requisite for subject \{2, 4, 5, 6, 7, 8\}, subject 2 can act as pre-requisite for \{4, 5, 7, 8\} and subject 3 can act as pre-requisite for \{5, 7\}.
Time Complexity
O(n) per test case