OH1DCARE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

MEDIUM

PREREQUISITES:

2SAT

PROBLEM:

Given a matrix C of size N\cdot M. Each cell of the matrix contains either a 0, 1 or null. In one move, you may invert all non-null values of a particular column.
Determine if it is possible to invert the columns in such a way that, there is atmost one 1 in each row at the end.

EXPLANATION:

It is immediately obvious that each column must be inverted at most once.
So, let’s define a binary array V, where V_y equals 1 if the y^{th} column should be inverted (and 0 otherwise). Then, V is a valid solution if there is atmost one 1 in the set \{C_{i,1}\oplus V_1,\dots,C_{i, M}\oplus V_M\} for all valid i.

How do we determine if a suitable array V exists?

Hint 1

The boolean criteria gives strong vibes of 2SAT.

Hint 2

To construct the clauses, we need to find a correlation between pairs of columns. In other words, does setting the value of V_i force a particular value to also be set on V_j (to ensure V is a valid solution)?

Solution

Consider some valid x such that C_{x,i} and C_{x,j} are non-null. Then, the following implications must hold for a valid solution (reasoning is trivial and left to the reader as an exercise):

  • (V_i=\neg C_{x,i}) \implies (V_j=C_{x,j})
  • (V_j=\neg C_{x,j}) \implies (V_i=C_{x,i})
Layman explanation

The above implications simply mean, if the value of C_{x,i} is 1 (after flipping the column V_i times), then the value of C_{x,j} (after flipping it’s column V_j times) must equal 0. And vice versa.

This can be equivalently written in disjunction form as (p \vee q) where:

  • p is \neg V_i if C_{x,i}=0, and V_i otherwise.
  • q is \neg V_j if C_{x,j}=0, and V_j otherwise.
Suboptimal Solution

For every valid x,i,j where C_{x,i} and C_{x,j} are non-null, add the clause (p\vee q) to the conjunction, where:

  • p is \neg V_i if C_{x,i}=0, and V_i otherwise.
  • q is \neg V_j if C_{x,j}=0, and V_j otherwise.

Then, run a standard 2SAT determiner to check if a valid solution exists.
While this works, the time complexity of the approach is O(N\cdot M^2) which is too large to pass for the given constraints.

However, it is possible to optimise this approach using lazy propogation. That is, instead of constructing clauses for every pair of cells in the same row, we only construct clauses for adjacent cells, in a way that allows them to implicitly propogate the other clauses.

Hint 3

Use the fact that, if C_{x,y} equals 1, then all C_{x,y'}\ (y<y') must equal 0. Can you build a chain of implications from this?

You will have to create several more variables for the CNF formula.

Solution

Apart from array V, we define boolean variables W and R.

Let W_{x,y} represent the (final) value of cell (x,y).
Let R_{x,y} represent if there exists a y'\ (y'<y) where W_{x,y'}=1. This variable, when set to True, will propagate the same to all subsequent cells, effectively ensuring no more cells in the row are set as 1.

Then, a conjunction of the following clauses over all valid x,y is sufficient to represent the problem (here, l represents the greatest index <y such that cell C_{x,l} is non-null):

  • (\neg R_{x,y}\vee \neg W_{x,y})

  • (\neg R_{x,l}\vee R_{x,y})

  • (\neg W_{x,l}\vee R_{x,y})

  • If C_{x,y}=0 \to (V_y\vee \neg W_{x,y}) and (\neg V_y\vee W_{x,y})

  • If C_{x,y}=1 \to (V_y\vee W_{x,y}) and (\neg V_y\vee \neg W_{x,y})

Explanation

The first clause says “if a preceding cell in this row is already set to 1, set W_{x,y} to 0”.

The second clause sets the value of all subsequent R_{x,y'} to 1 (recursively, propogated lazily) when R_{x,y} is 1. This, combined with the third clause - “if the previous cell in the row has value 1, set R_{x,y} to 1” - ensures each row has atmost one 1 in it.

The last two clauses define the relationship between the column inverting operations and the values of every cell in the corresponding column.

TIME COMPLEXITY:

There are a total of 5\cdot N\cdot M clauses and \approx 2\cdot N\cdot M variables. The time complexity to determine the satisfiability is therefore:

O(5\cdot N\cdot M + 2\cdot N\cdot M)\approx O(N\cdot M)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters