I've stumbled across this problem on CSES https://cses.fi/345/task/E/ and was wondering is it somehow reducible to 2-SAT with given constraints?
So, the problem states that you need to solve a 3-SAT given in a CNF form, albeit a special case, where:
- Each clause has exactly 3 distinct variables
- Each variable occurs at most 3 times in all clauses
I doubt that CSES would ask for a heuristic, solver like, approach but can't figure out how those new constraints help in creating a polynomial, possibly close to linear (due to size of input) solution.
Any help would be much appreciated :)