OJ Board

mf wrote:Nope. We're looking not just for some real-valued matrix, but for a "matrix of 0s and 1s".

If the equations have a unique solution, simply check if all variables are either 1,0
Otherwise, put free variables as 1 or 0. Then check if the rest of all variables have integral solutions.

It looks like very hard problem.
Even the following problem, which is a simplification of this one, is very hard: there is a set S of N points on plane, and the query is some circle; we should return number of points from S inside the circle. This problem (which is mentioned in Shamos, Preparata ...

I think this can transformed to a linear algebra problem trivially.

Hi,
1)Can you be more specific? Pre-processing can mean anything.
2) The forest generated by DFS traversal such that edges in forests are the forward edges in DFS.
3) I think the following link can help you.
http://www.student.cs.uwaterloo.ca/~cs3 ... Unit17.pdf

Cheers,