Editorial for DMOPC '21 Contest 1 P3 - Mystery DAG

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: 4fecta

This problem may seem intimidating at first, so let's identify some preliminary clues. First of all, note that the query limit of 3000 is quite close to 300 \log 300 with moderate overhead. If we recall algorithms which use \mathcal{O}(N \log N) 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 G_1 and G_2 such that both G_1 and G_2 are acyclic. Now, if we introduce some directed edges between G_1 and G_2, how can we ensure that the resulting graph is also acyclic? Well, we can simply direct all the edges such that they lead from G_1 to G_2! Bringing this back to the task at hand, if we query the set of nodes in G_2 as set A and the set of nodes in G_1 as B, we can just flip the direction of all the edges at the returned indices to ensure that all edges between G_1 and G_2 lead from G_1 to G_2.

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 \mathcal{O}(N \log N) 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 1 to N. These can each be expressed in \mathcal{O}(\log N) bits. Furthermore, for each pair of numbers i \neq j in this range, they must differ in at least one of the \mathcal{O}(\log N) bits.

Now, for the i-th of the \mathcal{O}(\log N) bits, let's make a query where a node belongs to set A if its number has the i-th bit equal to 0, or it belongs to set B otherwise. Then, for each edge that goes from set A to set B 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 i \neq j must differ by at least one bit, we know that we would have covered all possible pairs (and thus all possible edges) after the \mathcal{O}(\log N) queries. Since each query includes exactly N nodes, this solution also uses \mathcal{O}(N \log N) operations.

Thanks to Nils_Emmenegger for discovering this solution.


There are no comments at the moment.