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, there are only 6 possible permutations. Casework can be done for each of them.

Time Complexity: \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 with A_1, storing the result in an array (let's call it P). Let MIN be the smallest element in P and let MAX be the largest element in P. If MAX = N, this means that A_1 = 1. Otherwise, MIN = 1 \times A_1 which implies that MIN = A_1. Thus, we have found A_1.

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

Time Complexity: \mathcal{O}(N)


  • 11
    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:

    1. Query indices 1 and 2, 1 and 3, 2 and 3.
    2. Then you have A_1 \times A_2, A_1 \times A_3, and A_2 \times A_3, and you can solve the system of equations for A_1, A_2, and A_3.

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

    Finally, since A is a permutation of the first 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.