Editorial for DMOPC '20 Contest 6 P5 - Jennifer's Math Mystery

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ADMathNoob

We reformulate the conditions in the language of graph theory.

We are given a graph with N nodes and M edges. Each node i has a number x_i written on it. We are allowed to ask up to 2N-1 queries; each query allows us to know the AND or OR of the two values written on the endpoints of an edge. It is given that, regardless of the numbers in the list itself, we will be able to find all values x_i.

A critical observation is that this final condition implies that each connected component of the graph is not bipartite. How might we have discovered this fact?

Consider the case where all x_i are in the set \{0, 1\}. Without some specific structure, it may be possible to ensure that \displaystyle x_u \mathbin\& x_v = 0 \quad \mathrm{and} \quad x_u \mid x_v = 1 holds for all edges (u, v) in a component. We may consider making these equations hold since they are the "more common result" of their respective operations (AND and OR).

Indeed, if we label the nodes of the graph with 0 and 1 in a bipartite way, then all edges join nodes with a 0 and a 1, which makes the above equations hold. But swapping the 0's and 1's will yield the same results for all queries, which means it wouldn't be possible to find all x_i, contradicting the problem statement.

Thus, the problem is really telling us that each connected component has an odd cycle. How can we use this information? Note that \displaystyle (a \mathbin\& b) + (a \mid b) = a + b \quad\quad (\ast) since the number of ones for each bit is the same on both sides. (The proof is similar to how we can show that \gcd(m, n) \cdot \mathrm{lcm}(m, n) = m \cdot n for positive integers m and n; if you haven't seen these two identities before, try proving them!)

Thus, if we know some value x_u, then we can find the value of x_v for a neighbour v of u in two queries by rearranging the equation (\ast). Since the upper limit on queries is 2N-1, it seems likely that this fact will be helpful since we need to use about two queries to find each x_i. We might hope to be able to find the values on an odd cycle with k nodes in 2k-1 queries.

Without loss of generality, say that the nodes on the odd cycle in order are 1, 2, \dots, k, where k is odd.

With this, we are able to find all (x_i + x_{i+1}) for i = 1, 2, \dots, k in 2k queries. Using these k values, we can calculate all x_i using a prefix sum array. Depending on implementation, the (easily-computed) modular inverse of 2 \pmod{k} (which exists since k is odd) may be required.

Finally, to optimize this to use 2k-1 queries, note that the equation (\ast) still holds when we replace the + on both sides by \oplus (the bitwise XOR operator) by similar reasoning. Thus, we see that the XOR of all 2k queries is 0, so the answer to the 2k-th query can be computed as the XOR of the last 2k-1 responses.

The 30% subtask was intended to reward contestants that considered the smallest (valid) case, where the given graph is the complete graph K_3, which is a triangle. Moreover, once this case is solved, it becomes easier to notice that we can find all x_i where the i are the nodes of any odd cycle. Then, examining the problem statement more closely reveals that all components have an odd cycle, which leads to the full solution described above.

Finally, there are many successful approaches that can be used to solve this problem; please feel free to share any other methods in the comments, especially those that are simpler or more query-efficient than the one described here.


There are no comments at the moment.