## Editorial for DMOPC '21 Contest 1 P3 - Mystery DAG

**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:

This problem may seem intimidating at first, so let's identify some preliminary clues. First of all, note that the query limit of is quite close to with moderate overhead. If we recall algorithms which use operations (e.g. merge sort), we may discover the possibility of a divide-and-conquer based approach being applied here.

Let's assume we have 2 disjoint graphs and such that both and are acyclic. Now, if we introduce some directed edges between and , how can we ensure that the resulting graph is also acyclic? Well, we can simply direct all the edges such that they lead from to ! Bringing this back to the task at hand, if we query the set of nodes in as set and the set of nodes in as , we can just flip the direction of all the edges at the returned indices to ensure that all edges between and lead from to .

Now that we have a method to merge two DAGs into a single larger DAG, we can apply divide-and-conquer on the set of nodes to obtain a working solution using operations.

#### Alternate Solution

We devise a solution that orients all the edges from a smaller number to a larger number, for which it is easy to show acyclicity using monovariants. Consider the binary representations of the numbers from to . These can each be expressed in bits. Furthermore, for each pair of numbers in this range, they must differ in at least one of the bits.

Now, for the -th of the bits, let's make a query where a node belongs to set if its number has the -th bit equal to , or it belongs to set otherwise. Then, for each edge that goes from set to set or vice versa from the input, we flip it if it goes from a larger number to a smaller number (we can implicitly work out the orientations of these edges from the list of indices received from Siesta).

Since each pair must differ by at least one bit, we know that we would have covered all possible pairs (and thus all possible edges) after the queries. Since each query includes exactly nodes, this solution also uses operations.

Thanks to

for discovering this solution.
## Comments