DMOPC '21 Contest 1 P3 - Mystery DAG

View as PDF

Submit solution

Points: 12
Time limit: 2.0s
Memory limit: 256M

Problem types

You had a directed graph with N nodes and M edges, but forgot the orientation of each edge. That is, the i-th edge could either go from u_i to v_i or from v_i to u_i. Siesta still remembers the orientations, but she insists on keeping it a mystery and not telling you. Instead, she invites you to play the following detective game:

In one question to Siesta, you may ask about two sets of nodes A and B. In response, she will give you a list of all the edges that go from some node in set A to some node in set B. To challenge you further, she provides the extra constraint that the sum of the sizes of A and B over all questions must not exceed 3000.

Your task is to change the orientation of some subset of the edges in the graph such that the resulting graph is acyclic. Can you solve this problem?


This is an interactive problem. The first line contains 2 space-separated integers N (2 \le N \le 300) and M (1 \le M \le \frac{N(N-1)}{2}).

The next M lines each contain 2 space-separated integers u_i and v_i (1 \le u_i, v_i \le N), representing that the i-th edge either goes from u_i to v_i or from v_i to u_i. Each edge connects 2 distinct nodes, and there is at most one edge between any 2 nodes.

You will then begin interaction with Siesta. To ask her a question, you should print 3 lines to the output:

Line 1: ?, followed by a space, followed by 2 space-separated integers |A| and |B| (1 \le |A|, |B|).
Line 2: |A| space-separated integers a_i (1 \le i \le |A|), representing the nodes in set A.
Line 3: |B| space-separated integers b_i (1 \le i \le |B|), representing the nodes in set B.

Furthermore, 1 \le a_i, b_i \le N must hold, all a_i must be distinct, and all b_i must be distinct.

In response, you should read in one line from Siesta. This line will contain R, followed by R space-separated integers r_i (1 \le i \le R), representing the list of the indices of the edges in the graph that go from some node in set A to some node in set B.

If you believe you have a solution to the problem, you may output !, followed by a space, followed by a binary string of length M. The i-th character of this string should be 1 if the i-th edge should have its orientation changed, or 0 otherwise. You must terminate your program immediately after performing this operation.

If at any point your output is ill-formatted, you attempt an invalid question, or the sum of |A| + |B| exceeds 3000, Siesta will respond with -1. At this point your program should exit in order to receive a Wrong Answer verdict.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

>>> denotes your output. Do not print this out.

4 5
4 1
4 2
2 1
2 3
4 3
>>> ? 2 1
>>> 1 3
>>> 4
2 1 5
>>> ? 1 1
>>> 3
>>> 2
>>> ? 4 4
>>> 1 3 2 4
>>> 2 3 4 1
5 3 4 1 5 2
>>> ! 00101

Sample Explanation

The initial graph is as follows (note that you cannot directly infer the orientations of the edges from the initial input):

After changing the orientation of the 3-rd and 5-th edge, as specified in the last line of the sample interaction, the graph looks like this:

This interaction would receive an Accepted verdict, since the graph is indeed acyclic after changing the specified orientations, and the sum of |A| + |B| over all questions does not exceed 3000. Note that only changing the orientation of the 2-nd edge here would be an equally valid solution.


There are no comments at the moment.