Editorial for Wesley's Anger Contest 1 Problem 5 - Rule of Four
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
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.
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).
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 ).
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.
For the fifth subtask, we will use the same idea as the fourth subtask, however instead of performing a depth first or breadth first search to determine if the affirmative and negative vertices are reachable from each other, we will instead compute the transitive closure of the directed acyclic graph formed by the strongly connected components. If we use a 2D boolean array to store the transitive closure (where each boolean takes 1 byte), and assume (which means the directed acyclic graph will have vertices in the worst case), then this will take around 2.5 GB of memory, which exceeds the memory limit. Note that even though a boolean takes up 1 byte, we cannot manipulate the individual bits, wasting space. To reduce our memory usage, we will use a bitset instead, which will allow us to modify each of the 8 bits in a byte. This will take around 313 MB of memory, well within the memory limit.
From here, we can use dynamic programming on the directed acyclic graph to determine the components that are reachable from each other. For each component, we will compute the bitwise of all the bitsets of adjacent component, as well as the bitset of the current component. Now, the bit of the bitset will be if and only if component is reachable from component .
Time Complexity: (with a really good constant)