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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Since , there are only
possible permutations. Casework can be done for each of them.
Time Complexity:
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 with
, storing the result in an array (let's call it
). Let
be the smallest element in
and let
be the largest element in
. If
, this means that
. Otherwise,
which implies that
. Thus, we have found
.
Now that we have found , we can divide every element in
by it, and at this point, we have found every element in
.
Time Complexity:
Comments
There's an alternative solution that extends into the hard version quite nicely.
First, find three values using three queries:
With the value of
, use your remaining
queries to get
.
Finally, since
is a permutation of the first
integers,
. For the hard version, you can simply select different indices to find your first three values and query accordingly.