Krooger
December 3rd, 2009, 11:59 PM
So I have to take a basic 3-SAT problem and solve it in nlog(n) time, OR just n.
The variation is that you have an array of boolean values, lets call it B
If clause C contains Bi or ~Bi, and contains Bj or ~Bj, then abs|j-i| <= 10.
Sooo any Clause can only have boolean values that are MAX 10 index spaces away from eachother in the boolean array.
I been racking my brain trying to come up with something but... nothing.
My algorithm must decide if an assignement is possible and if it is, must find that assignment.
Any ideas? Thank You
The variation is that you have an array of boolean values, lets call it B
If clause C contains Bi or ~Bi, and contains Bj or ~Bj, then abs|j-i| <= 10.
Sooo any Clause can only have boolean values that are MAX 10 index spaces away from eachother in the boolean array.
I been racking my brain trying to come up with something but... nothing.
My algorithm must decide if an assignement is possible and if it is, must find that assignment.
Any ideas? Thank You