MVB's blog

Help with a 2SAT? Problem
By MVB, history, 6 months ago, In English

Hello! I have been stuck on this problem for a while. Here is what it asks:

Given an array, determine if it is possible to choose a set of distinct subarrays of length $$$2$$$ such that every index is taken at least once. A set of subarrays is considered distinct if no two subarrays have equal elements. For example, $$$[1,2],[1,2]$$$ is not a valid set, while $$$[1,3],[1,2]$$$ is.

As an example, let's consider the array $$$[1,2,1,2,3]$$$. We can choose $$$[1,2],[2,1],[2,3]$$$, corresponding to the indices $$$[1,2],[2,3],[4,5]$$$ (indexed from $$$1$$$).

The problem can be found here.

I have heard that this can be solved with 2SAT, but I have no idea how. I have never solved a 2SAT problem similar to this one, and I don't know what I am missing. Basically, I don't understand how to construct a graph that solves this task (or if it can be solved in another way).

Any help, similar problem(s), or hints would be much appreciated. Thanks!

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MVB (previous revision, new revision, compare).

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The nodes are the subarrays of length $$$2$$$.

  • For each element, you have to choose at least one subarray that covers it (condition: "at least one of $$$x_i$$$ and $$$x_j$$$").
  • For each distinct subarray, you can choose it at most once (condition: "at most one of $$$x_{i_1}, \dots, x_{i_k}$$$").

The first condition is an OR between two variables, the second is more complicated (it seems that you need to create $$$O(n^2)$$$ edges) but it is compatible with 2-SAT (for example, see the editorial of 1903F - Babysitting).

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot for laying out the conditions like that. I managed to solve it.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hey bro i want to use the flow like ford fulkerson. do youthink iits possible for this problem to use maybe dinitz algo??

→ Reply