CONSEL - Editorial

general
, , , ,
1

Links:
Contest
Practice

DIFFICULTY:

Hard

PREREQUISITES:

2-satisfiability: Tutorial

QUICK EXPLANATION:

This problem can be reduced to 2-satisfiability. Every constraint can be modelled in terms of a pair of implications which in turn can be written as a 2-sat clause. The choice of selecting a node or not can be seen as a boolean variable. To take care of property 3, we can build an auxiliary tree for each prime < N, and introduce an extra variable at each node in the tree which is
false only if no node is selected among the nodes in its subtree.

EXPLANATION:

Lets first focus on the first two properties:

For any integer 0 < A < N such that gcd(A,N) is 1, there exists a unique integer 0 < B < N such that A * B = 1 (mod N) (explanation). Hence, all nodes with value A such that gcd(A,N) != 1 are not affected by the first two properties and we need not select them in our subset, because adding new nodes always adds conflicts to the property 3.

For A such that gcd(A,N) is 1:

  1. If there does not exist any node with value B such that A * B = 1 (mod N), once again, we need not select nodes with such value A.
  2. If B is equal to A:
  • If there is only one node with the value A, again, we need not select it
  • If there are exactly two nodes with value A, we must select exactly one of the two nodes
  • If there are more than two nodes with this value, no valid subset exists
  • Otherwise, we either select all nodes with value A and no nodes with value B, or all nodes with value B and no nodes with value A

    • Above conditions can be modelled in terms of boolean satisfiability by treating the fact of selecting a node as a boolean variable. In Case 2.b, the value TRUE can represent the selection of first node, and FALSE, the selection of second node. Similarly, the same boolean variable is responsible for all nodes with values A and B.

    For property 3:
    If we select a node X with value A, we cannot select any of the nodes in its subtree (say with value B) such that gcd(A,B) > 1.

    This can be handled by adding a 2-sat clause between X and every such node in its subtree. However, this may result in O(N2) edges in the implication graph. To reduce the edges, for each prime < N, we build an auxiliary tree from nodes with values which are multiples of the prime. Now, we introduce an extra dummy variable at each node, and add the following implications for each node X and each of its children (say Y):

    ~X_dummy => ~Y_dummy
    X_var => ~Y_dummy
    ~X_dummy => ~X_var

    Hence, the total number of edges will now be O(N*log(MAX_VAL)) and the total time complexity is *O(N*log(MAX_VAL)log(N)) (for creating the auxiliary trees)

    NOTE: We were unable to create tests which force the O(N2) 2-sat construction to fail, hence an optimised implementation of that construction can run in time as well.

    Author’s Solution can be found here.

    1 Like