Editorial for An Animal Contest 5 P2 - Permutations & Products

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

Subtask 1

Since $N = 3$ ~N = 3~, there are only $6$ ~6~ possible permutations. Casework can be done for each of them.

Time Complexity: $\mathcal{O}(N!)$ ~\mathcal{O}(N!)~

Subtask 2

This editorial will highlight one of several solutions to this problem. If you have a different solution, feel free to share it in the comments!

We will query $A_2, A_3, \dots, A_N$ ~A_2, A_3, \dots, A_N~ with $A_1$ ~A_1~, storing the result in an array (let's call it $P$ ~P~). Let $MIN$ ~MIN~ be the smallest element in $P$ ~P~ and let $MAX$ ~MAX~ be the largest element in $P$ ~P~. If $MAX = N$ ~MAX = N~, this means that $A_1 = 1$ ~A_1 = 1~. Otherwise, $MIN = 1 \times A_1$ ~MIN = 1 \times A_1~ which implies that $MIN = A_1$ ~MIN = A_1~. Thus, we have found $A_1$ ~A_1~.

Now that we have found $A_1$ ~A_1~, we can divide every element in $P$ ~P~ by it, and at this point, we have found every element in $A$ ~A~.

Time Complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Comments

12
jeffreykaili commented on Feb. 3, 2022, 2:30 a.m. ← edited →
There's an alternative solution that extends into the hard version quite nicely.

First, find three values using three queries:

Query indices $1$ ~1~ and $2$ ~2~, $1$ ~1~ and $3$ ~3~, $2$ ~2~ and $3$ ~3~.

Then you have $A_1 \times A_2$ ~A_1 \times A_2~, $A_1 \times A_3$ ~A_1 \times A_3~, and $A_2 \times A_3$ ~A_2 \times A_3~, and you can solve the system of equations for $A_1$ ~A_1~, $A_2$ ~A_2~, and $A_3$ ~A_3~.

With the value of $A_1$ ~A_1~, use your remaining $N - 4$ ~N - 4~ queries to get $A_4, \ldots, A_{N-1}$ ~A_4, \ldots, A_{N-1}~.

Finally, since $A$ ~A~ is a permutation of the first $N$ ~N~ integers, $A_N = \frac{N(N+1)}{2} - \sum_{i=1}^{N-1} A_i$ . For the hard version, you can simply select different indices to find your first three values and query accordingly.