Editorial for An Animal Contest 1 P4 - Alpaca Arrays


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

Subtask 1

For each query, we can iterate through all the values of a and b such that a \cdot b = x in \mathcal{O}(\sqrt{X}) time. For each pair of a and b, we loop through indices l to r of the array to check whether both a and b are present within that range. If so, we can print YES.

Time Complexity: \mathcal{O}(Q \cdot \sqrt{X} \cdot N)

Subtask 2

We store the queries in an array and sort them by their r value for offline processing. Set an array arr where arr_i stores the most recent appearance of the number i. Initially we set all these values to 0, then for each query, we can update the index of the most recent appearance of all numbers which appear before or at the index r. To answer each query we iterate through all the values of a and b such that a \cdot b = x in \mathcal{O}(\sqrt{X}) time. For each pair (a, b), we check whether both arr_a and arr_b are less than l or not. If not, the answer to that query would be YES. Then, we just need to make sure that the answers are outputted in the correct order. This can be done by giving each query an id based on the order in which it is read from input.

Time Complexity: \mathcal{O}(Q\log Q + Q \cdot \sqrt{X})


Alternatively, there is another solution that does not require offline processing. Store the indices of the appearances of each number in separate lists. For each query, we can iterate through all the values of a and b such that a \cdot b = x in \mathcal{O}(\sqrt{X}) time. In the lists storing the appearances of each divisor, we binary search for the index that l would take if it were in the array and similarly for r. If the value of these two indices are the same, this means that there are no occurrences of that specific number between l and r. For both divisors, if the results from the previous step are not the same, we print YES.

Time Complexity: \mathcal{O}(Q \cdot \sqrt{X} \cdot \log N)


Comments

There are no comments at the moment.