## Puzzle : Goof ups by GOD

Well,

Coming directly to the point. Today’s puzzle was posted by manoj and answer was given by Saket. I am just copying it verbatim assuming that things are under creative commons license :D.

Problem :

You are given n balls. There are two type of information God has given to you.
Same(i,j) if ball “i” and “j” are same.
Different(i,j) if ball “i” and “j” are different.

Since the world is imperfect, obviously God has goofed up somewhere.
example
Same(1,2), Same(2,3), Different(1,3)
Obviously this is not consistent
But,
Same(1,2), Different(2,3)
is consistent as you “believe” that God will never assert “Same(1,3)”

But as I said God has goofed up somewhere and you have to pay the
price. And that too a computing price.
Given “m” such assertions can you find if the assertions are consistent.

Can you do it in O($m^2$) time?

Can you do it in O($m logn$) time?
Can you do it in O(m) time?

Solution :

I think O($m^2$) solution is quite easy to achieve for this problem.

Every ball is represented by a vertex, when we process the statement same(i,j) we add an edge between the two corresponding vertex. We process all same(x,y) statements like this. Now for the set to be consistent, there should not be a statement different(x’,y’) such that x’ and y’ are connected. There can be O(m) such statements, we can check each statement by a simple DFS, which will again take O(m) time. Thus giving us an O($m^2$) solution.

For the O(m log n) solution we can use the same edge structure, but additionally make use of the well-known Union-find data structure. Which gives O(log n) time for union / find. So we can insert O(m) edges for all same(x,y) calls in O(m log n) into the structure + for each different(x’,y’) use find, to check if both x’ and y’ belong to the same component (there can be O(m) such statements making the total time taken O(m log n)). The total time for the whole operation is thus O(m log n).

For the O(m) solution,

I think this problem in fact is same as the one addressed by union – find. Because if we have a O(m) solution to this problem, then we will also have an O(1) time union-find solution. But since the union find has a proven lower bound of inverse ackerman function (which although not constant, is extremely slow growing), this problem will also have a lower bound of O(m  α(n)).

Tags: , ,

### 5 Responses to “Puzzle : Goof ups by GOD”

I think a more interesting question to ask is: if given m assertions can k of them be satisfied?
Do you know an efficient way of doing this?

2. Pratik Poddar Says:

Interesting solution…
Thanx for that…

Just a small observation.. ofcourse the solution by union find is great… but in case the number of assertions we make are really exhaustive, i.e. for n balls, i.e m approximately equal to mn(n+1)/2, we can do it in O(n^2), hence O(m) by using table filling algorithm {as used in many Theory of Computation Algorithms}… I hope I am correct… This algorithm is O($n^2$)… Whether this is better than O($m\alpha(n)$) is debatable

3. Cristian Says:

Forgive me, maybe I didn’t understand the solutions right, but doesn’t any structure we use for representing the vertices and edges require initialization, meaning there is a hidden O(n) addition to all three methods? That would make the three running times O(m^2 + n), O(m log n + n) respectively O(m + n).

Secondly, if using a list of neighbors representation of a graph isn’t a pure O(m + n) solution obvious? Init of the graph is O(n), insertion of edges in the graph is O(1), then do a fill over connected components numbering each component increasingly, fill is O(m + n), then answer all queries in O(1) by checking the number of the nodes. That would make up for an O(m + n) algo.

Am I missing something guys?

4. Saurabh Joshi Says:

Well, because number of assertions m can be as much as O(n^2), and usually we only mention the dominating term in O-notation.

As you can see in the solution that O(m) is impossible due to lower bound on union-find algorithm. Solution O(m log n ) is also explained using union find. I don’t understand what do you mean by fill over connected components. In any case, you can not answer query in O(1).

5. Cristian Says:

True, union-find can’t do it in O(m). But union find solves a more general problem than this one. Here, you can consider the graph a constant, once you build up all the same() edges. I don’t do union-find.

By “fill” I mean a simple DFS in which you discover the connected components, labeling the nodes with the current component. Start at node one, do DFS labeling all nodes with one, advance to node two, do the labeling again, all this in O(m + n) (nowhere in this puzzle does it say that m is dominant so I’m keeping the n in there :-).

In the end each node is labeled with the number of the connected component it belongs to. You can answer different() queries in O(1).

Anyway, great blog guys, I’m having fun trying to solve the other problems. I’m glad I found it, keep posting 🙂 And many thanks!