Editorial for DMOPC '20 Contest 6 P5 - Jennifer's Math Mystery
Submitting an official solution before solving the problem yourself is a bannable offence.
We reformulate the conditions in the language of graph theory.
We are given a graph with nodes and edges. Each node has a number written on it. We are allowed to ask up to 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 .
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 are in the set . Without some specific structure, it may be possible to ensure that holds for all edges 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 , 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 since the number of ones for each bit is the same on both sides. (The proof is similar to how we can show that for positive integers and ; if you haven't seen these two identities before, try proving them!)
Thus, if we know some value , then we can find the value of for a neighbour of in two queries by rearranging the equation . Since the upper limit on queries is , it seems likely that this fact will be helpful since we need to use about two queries to find each . We might hope to be able to find the values on an odd cycle with nodes in queries.
Without loss of generality, say that the nodes on the odd cycle in order are , where is odd.
With this, we are able to find all for in queries. Using these values, we can calculate all using a prefix sum array. Depending on implementation, the (easily-computed) modular inverse of (which exists since is odd) may be required.
Finally, to optimize this to use queries, note that the equation still holds when we replace the on both sides by (the bitwise XOR operator) by similar reasoning. Thus, we see that the XOR of all queries is 0, so the answer to the -th query can be computed as the XOR of the last responses.
The 30% subtask was intended to reward contestants that considered the smallest (valid) case, where the given graph is the complete graph , which is a triangle. Moreover, once this case is solved, it becomes easier to notice that we can find all where the 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.