Increasing CP5 Lower Bound (Day 4)


2020-12-09 18:10 AKST

Increasing CP5 Lower Bound (Day 4)


2020-12-10 00:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -407 days 4:52:23

Time elapsed


Time remaining


Problem C
Find the Graph

Brandon Greg Jr. told you that he found an interesting undirected graph $G$. The graph has $n$ vertices labelled with the integers $1, 2, \ldots , n$. The graph is simple, meaning that each edge is between two distinct vertices, and no two edges are between the same pair of vertices.

Since Brandon doesn’t talk very much, you’ll have to play $3\, 000$ questions and solve this interactive problem to guess the graph. For each question, you may give him a subset $S\subset V(G)$ of the vertices. Brandon (the judge) would then tell you the number of edges between $S$ and $V(G)\setminus S$.

Can you guess the graph in at most $3\, 000$ queries?


The judge will start by outputting a single line containing a single number $n$ ($2\le n\le 50$), the number of vertices in the graph.

For each query, you may output one of the following:

  • ? $k$ $v_1$ $v_2$ $\dots $ $v_ k$ – If you output a question mark followed by an integer $k$ ($1\le k\le n$) and the indices of $k$ vertices, the judge will reply with the number of edges in the cut between $S = \{ v_1, v_2, \dots , v_ k\} $ and the remaining $n-k$ vertices in $V(G)\setminus S$. If your input is malformed, the judge will output $-1$. If you receive a reply of $-1$, please terminate your program immediately, or you may get an unexpected verdict.

  • ! – After outputting an exclamation mark, you must output the adjacency matrix of the graph on $n$ lines, each containing $n$ numbers. The $j$-th number on the $i$-th line should be $1$ if there is an edge between vertices $i$ and $j$, or $0$ otherwise. Your program must terminate immediately after outputting this matrix.

You may output no more than $3\, 000$ queries beginning with ?. Remember to flush your output after each query. The sample input and output only serve to show how one should interact with the judge, and the empty lines are for easier reading.

Read Sample Interaction 1 Write
? 3 1 2 3
? 4 1 4 3 2
? 2 1 3
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0
Read Sample Interaction 2 Write