MVB's blog

By MVB, history, 5 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!

Full text and comments »

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