Fighting Over a Duster

Subtask 1: Generate all possible subset of students. For all possible subset of students, find what's the maximum number of teachers you can make happy.

Subtask 2: Generate all possible subsets of teachers and see what's the maximum set where no teacher opposes each other.

Subtask 3: See that two teachers from same section will not contradict each other. So, take all the subsets(including empty set) of teachers from the section with less teacher, and see how many of the other section Can be satisfied if we take selected ones for sure.

Subtask 4: This problem can be converted to a edge cover problem. We have to maximise the number of happy teachers, we can interpret it as minimise number of unhappy teachers. Now if two teacher disagree with each other than we can take one but not the other. So, this is a edge cover problem, which can be solved using Bipartite matching/ Flow. Answer is n-edge cover.