ZIO08002 - Editorial

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 :

  1. X before Y
  2. X after Y

Here is how we are going to fill the table for the given things.

  1. X is a prerequisite of Y , so in yth row we should add X to the prerequisite list ( 2nd column )
  2. 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

  1. 4 before 5 → put 4 in 5th row 2nd column
  2. 2 after 5 → put 5 in the 2nd row 2nd column
  3. 4 before 2 → put 4 in the 2nd row 2nd column
  4. 6 after 7 → put 7 in the 6th row 2nd column
  5. 1 after 2 → put 2 in the 1st row 2nd column
  6. 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 :slight_smile: