Problem E. Monotone Subsequence

Suppose you made a query $$$[i_1, i_2, \ldots, i_k]$$$ and got a response $$$[j_1, j_2, \ldots, j_c]$$$. From the definition of visible skyscrapers, you can tell $$$i_1 = j_1$$$, and the following holds:

Based on this, think about the following algorithm:

• Initially $$$S_0 = \{ 1, 2, \ldots, n^2 + 1 \}$$$.
• Do the following $$$n$$$ times. In the $$$r$$$-th round $$$(1 \le r \le n)$$$, make a query consisting of all indices in $$$S_{r-1}$$$. Suppose you get a response $$$[j_1, j_2, \ldots, j_c]$$$. If $$$c \ge n+1$$$, you take any subsequence of length $$$n+1$$$ out of the response and make it an answer (because it's clearly increasing), then quit. Otherwise, $$$S_r = S_{r-1} \setminus \{ j_u \; | \; 1 \le u \le c \}$$$, then repeat.

Let's say you have completed $$$n$$$ rounds without making an answer. Clearly $$$S_0 \supset S_1 \supset \cdots \supset S_n$$$. Furthermore, $$$\left| S_{r-1} \right| - \left| S_{r} \right| \le n$$$, thus $$$\left| S_n \right| \ge (n^2 + 1) - n \cdot n = 1$$$.

Consider a directed graph $$$G$$$ consisting of $$$n^2 + 1$$$ vertices, initially with no edges. In round $$$r$$$, for every $$$i \in S_r$$$, there exists $$$j \in S_{r-1} \setminus S_{r}$$$ that satisfies $$$j \lt i$$$ and $$$p_j \gt p_i$$$, according to the relationship stated above. For every such $$$(i, j)$$$, add an edge $$$(j, i)$$$ to $$$G$$$. Then, for every $$$i \in S_r$$$, there is a path of length $$$r$$$ in $$$G$$$, ending at the vertex $$$i$$$ (this can be easily proven by induction). Therefore, after all rounds are processed, there is a path of length $$$n$$$ in $$$G$$$, ending at a vertex $$$i$$$ for any $$$i \in S_n$$$. Take any such path, then the $$$n + 1$$$ vertices in that path is an acceptable answer, because it forms a decreasing sequence.

Implementation note: The following is an easy way to find the final path. First, create an array $$$b = [-1, -1, \ldots, -1]$$$ of length $$$n^2 + 1$$$. For every round, record back edges: do $$$b[i] := j$$$ for every edge $$$(j, i)$$$ added to $$$G$$$. Then you can backtrack and recover the path, starting from any vertex in $$$S_n$$$.