### MVB's blog

By MVB, history, 3 months ago,

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!

• +13

 » 3 months ago, # |   0 Auto comment: topic has been updated by MVB (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   0 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).
•  » » 2 months ago, # ^ |   0 Thanks a lot for laying out the conditions like that. I managed to solve it.
 » 2 months ago, # |   0 hey bro i want to use the flow like ford fulkerson. do youthink iits possible for this problem to use maybe dinitz algo??