Proceed with the above logic of 2D array and only fill the matrix considering only the equality constraints ( xi=xj) Using the Floyd warshall All pair shortest path algorithm, we can know the all reachable places from every other place. Now fill the matrix as per the inequality constraints(xi!=xj) and whenever an overwrite occurs we will know that its not possible to satisfy all constraints.
Although this will shoot up our time complexity to O(n^3) because of Floyd Warshal algorithm. Comments welcome. Anurag Sharma On Wed, Jun 9, 2010 at 3:42 PM, jaladhi dave <jaladhi.k.d...@gmail.com>wrote: > Using an n*n array, am afraid, will not solve the problem, since its not > capable to capture transitivity. > > Consider the case: > > v1=v2 > v3=v2 > v3!=v1 > > we will place 0 in arr(1,2) arr(2,1) for v1=v2 > we will place 0 in arr(2,3) arr(3,2) for v3=v2 > and place 1 in arr(1,3) and arr(3,1) for v3!=v1. > > no overwrite :( and still the constraints cannot be satisfied. > > -jkd > > > > > On Tue, Jun 8, 2010 at 10:07 PM, Minotauraus <anike...@gmail.com> wrote: > >> Use a n x n array. >> initialize with -1 (don't care = no constraints). If there is an >> equality constraint, set to 1, if >> explicity non-equality constraint is expected, replace with 0. While >> doing either of these if >> you come across a situation where 0 has to be overwritten by 1 or 1 >> has to be overwritten by 0, >> the system constraints cannot be satisfied, else all is well. Space >> required = n^2 bytes. >> Time complexity = O(c) where c= number of constraints for the system. >> Therefore, independent of the number of variables. >> >> >> You can do this with hash tables too and probably save memory. Here >> you'll use not store = -1 = don't care. >> >> -Minotauraus. >> >> On Jun 7, 12:16 pm, divya <sweetdivya....@gmail.com> wrote: >> > Here's a problem that occurs in automatic program analysis. For a set >> > of variables x1; ...... ; xn, you are given some equality constraints, >> > of the form "xi = xj" and some dis equality constraints, of the form >> > "xi != xj" Is it possible to satisfy all of them? Give an efficient >> > algorithm that takes as input m constraints over n variables and >> > decides whether the constraints can be satisfied. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
