Editorial for DMOPC '17 Contest 5 P6 - Bridges

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

There is no intended solution for the first subtask.

For the second subtask, specific information can be gained by asking an order, then swapping two consecutive elements of this order and asking that. In particular, consider the queries n-1 n-2 ... 4 3 2 1 and n-1 n-2 ... 4 3 1 2. Let the answers to these two queries by $A_1$ $A_{1}$ and $A_2$ $A_{2}$ respectively. Let bridge $X$ $X$ be the leftmost bridge which has not yet been built when bridge $1$ $1$ is built in the advisor's order. It can be shown that if $A_1 \ge A_2$ $A_{1} \geq A_{2}$ , then $X$ $X$ must be $2$ $2$ , otherwise, $v_2 + v_3 + \dots + v_X = \frac{A_2-A_1+2v_1v_2}{2v_1}$ $v_{2} + v_{3} + \dots + v_{X} = \frac{A_{2} - A_{1} + 2 v_{1} v_{2}}{2 v_{1}}$ (it is possible for $X$ $X$ to be $n$ $n$ , in which case, bridge $1$ $1$ is the last bridge to be built).

So now, we know that no bridge with index between $1$ $1$ and $X$ $X$ can be built after bridge $1$ $1$ and before bridge $X$ $X$ . We now repeat this solution for the bridges from $2$ $2$ to $X-1$ $X - 1$ and the bridges from $X+1$ $X + 1$ to $N-1$ $N - 1$ . We also have to update the $v$ $v$ array and merge it appropriately. Clearly this solution requires less than $2N$ $2 N$ queries. The time complexity is unimportant, it is at the very most $\mathcal O(QN)$ $O (Q N)$ .

Comments

There are no comments at the moment.