## Editorial for Wesley's Anger Contest 1 Problem 5 - Rule of Four

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: wleung_bvg

#### Solution Sketch

For the first subtask, we can use a bitmask technique to iterate through all possible boolean assignments, and check in time if all requirements are met. To determine the actual solution, consider the bitwise of all masks where the requirements are met. If the bit is , then student must go on the trip. Now consider the bitwise of all masks where the requirements are met. If the bit is , then student must not go on the trip. All other students are indeterminate.

Time Complexity:

For the second subtask, consider a graph with students as vertices and requirements as edges. Note that at most once vertex of each edge can be selected. Here, it is sufficient to determine if the graph is bipartite, which can be done with a breadth first search. Note that there will never be a way to determine for sure if a student is going on the trip with for this subtask.

Time Complexity:

For the third subtask, we can create the graph the same way for PARTNERS requirements. For FRIENDS requirements, since both students must be assigned the same value, we can merge the two vertices into a single vertex (using union find) before performing the bipartite check. Finally, we must check if there is a boolean assignment to the bipartite graph such that all students who must go on the trip are on the same side. From each student that must go on the trip, we will perform a depth first search on the graph and assign boolean values based on the parity of the current depth. Once this is done, if there are any contradictions in the value assignment, then there is no solution. Otherwise, we can determine the answer by looking the assigned value for each student (with students with no assigned value being indeterminate).

Time Complexity:

For the fourth subtask, the question is very similar to the 2-SAT problem. Each requirement can be reduced to conjunctive normal form (including the requirement that a student must go on the trip). From here, we can create an implication graph and compute the strongly connected components of the graph in time. As long as affirmative and negative vertices in the implication graph are not in the same strongly connected component, then the requirements can all be met.

To determine the actual solution, recall that in the implication graph, all vertices in the same strongly connected component must have the same boolean value. A directed edge from to means that if is true, then must also be true. Since the affirmative and negative vertices cannot be the same value, if one is reachable from the other, then the first must be assigned false, and the second must be assigned true. This can be done with a depth first or breadth first search for each student. This takes time in total.

Next, we will mark the strongly connected component of the affirmative vertices of students that must go on the trip as true. and mark the strongly connected component of the negative vertices of students that must go on the trip as false. As long as there is a solution, this should not contradict the previous assignments. All vertices that are reachable from a vertex assigned true, must also be true, and all vertices that can reach a false vertex must also be false. However, a useful property of implication graphs is that is is skew-symmetric. This means that for some literals and (which may or may not contain negations), if there is a path from to , then there is a path from to . Proof is left as an exercise for the reader. Thus, if is reachable from , then is reachable from . It follows that if is reachable from (meaning is true), then is reachable from (meaning is also true). So checking the condition in the previous paragraph suffices and this paragraph can be ignored (thank you Dormi).

Once this is done, it should be the case for all vertices that if either the affirmative of negative vertex of a student is assigned a value, the other vertex has the opposite value. All other vertices cannot have their value determined.

Alternatively, the standard 2-SAT algorithm can first be run on the initial implication graph to determine if the all the requirements can be met. Then for each person, we will create a new graph formed by the initial graph, with the added constraint that the student must go on the trip. The same can be done for the constraint the the student must not go on the trip. If both can be satisfied, then it cannot be determined if the student can go on the trip or not. Otherwise, the answer will be whichever constraint allowed the trip requirements to be met.

Time Complexity: