PROBLEM LINK:
Author: Lewin Gan
Testers: Kamil Dębowski
Editorialist: Lewin Gan
DIFFICULTY:
Hard
PREREQUISITES:
Graphs
PROBLEM:
Find out if there exists a common node.
QUICK EXPLANATION:
If there exists an intersection, it can only exist at one node. In general, the problem of determining if two bitstrings intersect requires Omega(n) bits of communication. However, we can use the fact that this is a very specialized case to reduce the number of bits.
EXPLANATION:
This is called a “communication problem” in general. Typically, person A is given some information and person B is given some information, and they would like to compute some known function with both inputs, with as little communication as possible. The translation function is used to denote the communication channel, but this problem may have a better premise if we had the contestant program interacting with itself with two different initial inputs.
Anyways, onto the solution, let’s see how we can reduce the number of questions we need. We follow the procedure:
-
If there exists a node in Alice’s clique with degree < n/2, ask about that node. If it is in Bob’s independent set, we are done. Otherwise, we can delete all non-neighbors of this node in both graphs and recurse on this smaller graph.
-
If there exists a node in Bob’s independent set with degree >= n/2, ask about that node. If it is in Alice
s clique, we are done. Otherwise, we can delete all neighbors of this node in both graphs and recurse on this smaller graph. -
Otherwise, we know for sure there is no intersection between the sets, since all of Alice’s nodes have degree >= n/2 and all of Bob’s nodes have degree < n/2.
We can see that at each iteration, we halve the graph size, and we never delete a node that could be part of the intersection, so this takes at most log_2(n) questions, which fits within the limit.