Editorial for An Animal Contest 5 P2 - Permutations & Products - Olympiads Online Judge

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!)$ $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$ $M I N$ be the smallest element in $P$ $P$ and let $MAX$ $M A X$ be the largest element in $P$ $P$ . If $MAX = N$ $M A X = N$ , this means that $A_1 = 1$ $A_{1} = 1$ . Otherwise, $MIN = 1 \times A_1$ $M I N = 1 \times A_{1}$ which implies that $MIN = A_1$ $M I N = 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)$ $O (N)$

Comments

13
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}, \dots, 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$ $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.