Ninja and his Courses

Hard
0/120
Average time to solve is 50m
19 upvotes
Asked in company
Apple

Problem statement

You are going to study at Coding Ninja Institute. There are ‘N’ courses in this institute with some dependencies. You have been given a ‘DEPENDENCIES’ array/list of size ‘M’ where ‘DEPENDENCIES[i]’ is equal to [‘Xi’, ‘Yi’] representing that the course ‘Xi’ must be taken before the course ‘Yi’.

In one semester, you can take at most ‘K’ courses. So, you have to find the minimum number of semesters he takes all the courses.

Note: It is guaranteed that you can take all the courses in some way.

For example:

Let‘N’ = 3 , ‘K’ = 1 and ‘DEPENDENCIES’ = [ [1, 2] [2, 3] ].

In this example, if you want to take ‘COURSE_3’ then first you have to take ‘COURSE_2’ in the previous semester. If you want to take ‘COURSE_2’, then first you have to take ‘COURSE_1’ in the previous semester.
The value of ‘K’ is 1 which means in a semester we can choose at most 1 course.
Detailed explanation ( Input/output format, Notes, Images )
Input Format
The first line of input contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains three single space-separated integers ‘N’,‘M’ and ‘K’ represent the number of courses, number of dependencies and maximum courses that you can take in one semester respectively. 

The next ‘N’ line of each test case contains two single space-separated integers ‘X’ and ‘Y’ representing that the course ‘X’ must be taken before the course ‘Y’.
Output Format :
For each test case, print the minimum number of semesters required to take all the courses.

Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 15
0 <= ‘M’ <= ‘N’ * (‘N’ - 1)/2
1 <= ‘X’, ‘Y’ and ‘K’ <= ‘N’ 

Time Limit: 1 second
Sample Input 1:
2
4 3 2
2 1
3 1
1 4
5 0 2
Sample Output 1:
3
3

Explanation for Sample Output 1:

For sample test case 1: 

In the first semester we can choose ‘COURSE_2’ and ‘COURSE_3’ as these are not dependent on other courses. The value of ‘K’ is 2 which means in a semester we can choose at most 2 courses. So in the first semester, we choose these two courses.

After that in the second semester:

In the second semester, we can choose only the ‘COURSE_1’ as this course is not dependent on other courses. So in the first semester, we choose only one course.

After that in the third semester:

In the third semester, only one course is left i.e ‘COURSE_4’.So in the third semester, we choose the last course.

So, the minimum number of semesters required to take all the courses is 3.

For sample test case 2:

In this sample test case, no course is dependent on each other i.e all courses are independent. The value of ‘K’ is 2 which means in a semester we can choose at most 2 courses.

So in the first semester, we choose ‘COURSE_1’ and ‘COURSE_2’.
In the second semester, we choose ‘COURSE_3’ and ‘COURSE_4’.
In the third semester, we choose the last course i.e. ‘COURSE_5’.

So, the minimum number of semesters required to take all the courses is 3.
Sample Input 2:
1
5 4 2
2 1
3 1
4 1
1 5
Sample Output 2:
4

Explanation for Sample Output 2:

For sample test case 1: 

In the first semester, we can choose ‘COURSE_2’, ‘COURSE_3’ and  ‘COURSE_4’ as these are not dependent on other courses. The value of ‘K’ is 2 which means in a semester we can choose at most 2 courses. So in the first semester, let us assume we choose ‘COURSE_2’ and ‘COURSE_3’.

After the first semester:

In the second semester, we can choose only the ‘COURSE_4’ as this course is not dependent on other courses. So in the second semester, we choose only one course.

After that in the second semester:

In the third semester, we can choose only the ‘COURSE_1’ as this course is not dependent on other courses. So in the third semester, we choose only one course.

After that in the third semester:

In the fourth semester, only one course is left i.e ‘COURSE_5’.So in the fourth semester, we choose the last course.

So, the minimum number of semesters required to take all the courses is 4.
Hint

Think of the DP with a bit masking approach

Approaches (1)
DP with Bit Masking

As we know we can only take a course which is not dependent on any other course. So first we make a graph having edges ‘DEPENDENCIES[i]’ and nodes represent each course. Then we find all the nodes whose in-degree is 0 i.e. these nodes don’t depend on any other nodes. If the nodes are less than ‘K’ then we take all the nodes and subtract the indegree of all the nodes which are connected through these nodes. Else we are trying to select ‘K’ nodes by all possible ways from the current set of nodes and find our answer.

 

Here is the algorithm:

  1. We declare a ‘DP’ array/list where ‘DP[i]’ represents the minimum semesters required to take all the courses.
  2. We declare a ‘GRAPH’ list/vector and we make this graph by ‘DEPENDENCIES’ array/list where ‘DEPENDENCIES[i]’  represents the edge of this ‘GRAPH’.
  3. We declare a variable ‘MASK’ in which stores all the courses taken by us till now.
  4. We call our helper function ‘minSemHepler(‘MASK’).
  5. Finally, we return the answer which is calculated by our helper function.

minSemHepler(‘MASK’)

  1. Base case: If all courses are taken:
    1. Return 0.
  2. If ‘DP[‘MASK’]’ != -1 i.e if we previously calculated the result for these courses:
    1. Return ‘DP[‘MASK’]’.
  3. We declare an ‘INDEGREE’ list/vector in which we store that the particular course is dependent on how many other courses.
  4. We run a loop for ‘i’ = 0 to ‘N’:
    1. If the current course is already taken:
      1. Continue.
    2. We run a loop for ‘j’ = 0 to ‘GRAPH[i].size()’:
      1. ‘INDEGREE[i] ++’.
  5. We declare a variable ‘AVIL_MASK’ in which we store which courses are left behind that are not taken by you till now.
  6. We run a loop for ‘i’ =  0 to ‘N’:
    1. If ‘INDEGREE[i] is 0 and ‘i’th bit in ‘MASK’ is not set:
      1. Set the ‘’’h bit in ‘AVIL_MASK’.
  7. We declare a variable ‘TEMP_MASK’ initialized with ‘AVIL_MASK’.
  8. Count the number of set bits in ‘AVIL_MASK’.
  9. If the number of bits less than or equal to ‘K’:
    1. Take all the courses.
  10. Else:
    1. Check all possible combinations of ‘K’ set bits from the ‘AVIL_MASK’ and calculate the answer.
  11. Store the answer in ‘DP[mask]’ and return ‘DP[mask]’.
Time Complexity

O(3 ^ N) where ‘N’ represents the number of courses.

 

Let’s assume if ‘MASK’ has ‘K’ set bits, Then it will have 2 ^ K subtasks.

So we have a total of C(‘N’, ‘K’) combinations.

Then the total number of combinations for all masks will be 

 ∑ ‘K’ = 0… ‘N’ (C(‘N’, ‘K’) * 2 ^ ‘K’).

By binomial coefficients, ∑ ‘K’ = 0… ‘N’ (C(‘N’, ‘K’) * 2 ^ ‘K’) = 3 ^ ‘N’.

Space Complexity

O(2 ^ N) where ‘N’ represents the number of courses.

 

There are at most ‘N’ different function calls stored in the recursion stack. We are declaring a ‘DP’ array/list of size 2 ^ N. We are also declaring an ‘INDEGREE’ array/list and a ‘GRAPH’ array/list both of size ‘N’. Hence the overall space complexity is O(2 ^ N).

Code Solution
(100% EXP penalty)
Ninja and his Courses
Full screen
Console