Editorialist : Sudheera Y S
Problem Link : ZIO 2008 Problem 2
Prerequisites : Representation , Greedy
Problem statement :
There are some courses to be completed , and there are some prerequisites for some courses i.e you can take some course only after completing some other course . In one semester you can take as many courses as you want , but if you take some course , then that means that you have finished all the prerequisites of that course . Find the minimum number of semesters needed to complete all the courses satisfying the given condition.
Idea :
First , we will make a table which shows for any particular course which all courses are prerequisites for that particular course ( like an adjacency list ). Once we have the table , we will find the number of courses which don’t have any prerequisites and take all of them in the next semester and once we take that course , we will delete that course from the prerequisites of any other course if any ( so we will get to know which all courses we can do in the next semester ) .
Subtask A :
So first , let us make the table of the prerequisites .
In the first column we will have all the courses ( 10 in this case ) and in the second column we will have all the prerequisites of that course )
The initial would look something like this
| 1 | |
|---|---|
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 |
So now let us fill the conditions one by one .
As we can see in the input , there are two types of given input :
- X before Y
- X after Y
Here is how we are going to fill the table for the given things.
- X is a prerequisite of Y , so in yth row we should add X to the prerequisite list ( 2nd column )
- Y is a prerequisite of X , so in xth row we should add Y to the prerequisite list ( 2nd column )
So now doing like this, let us take one by one and fill the table
- 4 before 5 → put 4 in 5th row 2nd column
- 2 after 5 → put 5 in the 2nd row 2nd column
- 4 before 2 → put 4 in the 2nd row 2nd column
- 6 after 7 → put 7 in the 6th row 2nd column
- 1 after 2 → put 2 in the 1st row 2nd column
- 2 before 3 → put 2 in the 3rd row 2nd column
.
.
.
So on ……
Now our final table looks like :
| 1 | 2,3,6 |
|---|---|
| 2 | 5,4,7 |
| 3 | 2,4 |
| 4 | - |
| 5 | 4 |
| 6 | 7 |
| 7 | - |
| 8 | 1 |
| 9 | 10,8,1 |
| 10 | 2 |
Now here is our table .
Now let us start finding our answer .
4,7 Doesn’t have any prerequisite so we will do both of them in our first semester
1st Semester → 4,7
Now we can remove 4,7 from all the prerequisites ex . 5,6 …
And our table would look something like this :
| 1 | 2,3,6 |
|---|---|
| 2 | 5 |
| 3 | 2 |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | 1 |
| 9 | 10,8,1 |
| 10 | 2 |
Now in the second semester we can do all those which are not yet done and those which doesnt have any prerequisite .
In this case it is 5,6
Second semester → 5,6
Now as usual we will remove 5,6 from the prerequisite if any
Our table would look something like this :
| 1 | 2,3 |
|---|---|
| 2 | - |
| 3 | 2 |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | 1 |
| 9 | 10,8,1 |
| 10 | 2 |
Third semester → 2
We will remove 2 from all the prerequisite table and our new table would look something like this :
| 1 | 3 |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | 1 |
| 9 | 10,8,1 |
| 10 | - |
Fourth semester → 3,10
We will remove 3 and 10 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | 1 |
| 9 | 8,1 |
| 10 | - |
Fifth semester → 1
We will remove 1 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | - |
| 9 | 8 |
| 10 | - |
Sixth semester → 8
We will remove 8 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | - |
| 9 | - |
| 10 | - |
Seventh semester → 9
Now we see that we have completed all the courses and here we stop and we took seven semesters so our answer would be 7
Answer : 7
Subtask B :
There are total of 10 tasks so there would be 10 rows in our table and once we write all the prerequisites in the table , our table would look something like this :
| 1 | 8 |
|---|---|
| 2 | 6,9 |
| 3 | 8,2,9 |
| 4 | 3,10,1,8 |
| 5 | 1 |
| 6 | - |
| 7 | 4,1 |
| 8 | 9 |
| 9 | 6 |
| 10 | 2 |
First semester → 6
We will remove 6 from all the prerequisite table and our new table would look something like this :
| 1 | 8 |
|---|---|
| 2 | 9 |
| 3 | 8,2,9 |
| 4 | 3,10,1,8 |
| 5 | 1 |
| 6 | - |
| 7 | 4,1 |
| 8 | 9 |
| 9 | - |
| 10 | 2 |
Second semester → 9
We will remove 9 from all the prerequisite table and our new table would look something like this :
| 1 | 8 |
|---|---|
| 2 | - |
| 3 | 8,2 |
| 4 | 3,10,1,8 |
| 5 | 1 |
| 6 | - |
| 7 | 4,1 |
| 8 | - |
| 9 | - |
| 10 | 2 |
Third semester → 8,2
We will remove 8 and 2 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | 3,10,1 |
| 5 | 1 |
| 6 | - |
| 7 | 4,1 |
| 8 | - |
| 9 | - |
| 10 | - |
Fourth semester → 10,3,1
We will remove 10,3 and 2 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | 4 |
| 8 | - |
| 9 | - |
| 10 | - |
Fifth semester → 5,4
We will remove 5 and 2 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | - |
| 9 | - |
| 10 | - |
Sixth semester → 7
Nowe we have completed all the courses and we took 6 semesters to complete it so our answer would be 6
Answer : 6
Subtask C :
We see that there are total of 10 courses so there would be 10 rows in our table and after filling the prerequisites , our table would look something like this :
| 1 | 2,7,8 |
|---|---|
| 2 | 4 |
| 3 | 5 |
| 4 | 5 |
| 5 | - |
| 6 | 4 |
| 7 | 3 |
| 8 | 9 |
| 9 | 3 |
| 10 | 6,3,2 |
First semester → 5
We will remove 5 from all the prerequisite table and our new table would look something like this :
| 1 | 2,7,8 |
|---|---|
| 2 | 4 |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | 4 |
| 7 | 3 |
| 8 | 9 |
| 9 | 3 |
| 10 | 6,3,2 |
Second semester → 3,4
We will remove 3 and 4 from all the prerequisite table and our new table would look something like this :
| 1 | 2,7,8 |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | 9 |
| 9 | - |
| 10 | 6,2 |
Third semester → 6,7,2,9
We will remove 6,7,2 and 9 from all the prerequisite table and our new table would look something like this :
| 1 | 8 |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | - |
| 9 | - |
| 10 | - |
Fourth semester → 8,10
We will remove 8 and 10 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | - |
| 9 | - |
| 10 | - |
Fifth semester → 1
Now we see that all the courses are completed and we can stop here . We took 5 semesters to complete all the courses therefore the answer is 5
Answer : 5
Subtask D :
There are a total of 10 courses therefore the number of rows in our table would be 10 . After filling the table with the prerequisites our answer would look something like this :
| 1 | 2,4 |
|---|---|
| 2 | 3 |
| 3 | 4,9 |
| 4 | - |
| 5 | 2 |
| 6 | 5,2 |
| 7 | 6 |
| 8 | 1,9,10,5 |
| 9 | - |
| 10 | 4,7 |
First semester → 4,9
We will remove 4 and 9 from all the prerequisite table and our new table would look something like this :
| 1 | 2 |
|---|---|
| 2 | 3 |
| 3 | - |
| 4 | - |
| 5 | 2 |
| 6 | 5,2 |
| 7 | 6 |
| 8 | 1,10,5 |
| 9 | - |
| 10 | 7 |
Second semester → 3
We will remove 3 from all the prerequisite table and our new table would look something like this :
| 1 | 2 |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | 2 |
| 6 | 5,2 |
| 7 | 6 |
| 8 | 1,10,5 |
| 9 | - |
| 10 | 7 |
Third semester → 2
We will remove 2 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | 2 |
| 7 | 6 |
| 8 | 1,10,5 |
| 9 | - |
| 10 | 7 |
Fourth semester → 1,5
We will remove 1 and 5 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | 6 |
| 8 | 10 |
| 9 | - |
| 10 | 7 |
Fifth semester → 6
We will remove 6 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | 10 |
| 9 | - |
| 10 | 7 |
Sixth semester → 7
We will remove 7 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | 10 |
| 9 | - |
| 10 | - |
Seventh semester → 10
We will remove 10 from all the prerequisite table and our new table would look something like this :
| 1 | - |
|---|---|
| 2 | - |
| 3 | - |
| 4 | - |
| 5 | - |
| 6 | - |
| 7 | - |
| 8 | - |
| 9 | - |
| 10 | - |
Eight semester → 8
Now we see that all the courses are completed and here we can stop and we took eight semesters to finish all the courses therefore our answer is 8
Answer : 8
Hope you understood 
