Editorial for An Animal Contest 4 P2 - Lavish Lights

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

Solution 1:

We can solve this problem for each query by finding the first prefix LCM P such that P does not divide t_i. If such a P does not exist, that means that all lights are on at time t_i (t_i is a multiple of all integers in array a), and we can output -1.

To answer these queries efficiently, we can construct a prefix LCM array, stopping when the prefix LCM exceeds the maximum allowed t_i value, 10^9. For each query, we can run binary search and check if t_i divides all numbers up to some index idx.

Be careful of the case when t_i = 0; 0 is a multiple of all integers.

Time Complexity: \mathcal{O}(N \log 10^9 + Q \log N)

Solution 2:

If binary search isn't for you, observe that there are only a maximum of around \log 10^9 positions j where the light at position j will be the first to be off. We can find these positions by considering the prefix LCM and then for each query we can run linear search over these positions.

Again, be careful about edge cases such as when t_i = 0.

Time Complexity: \mathcal{O}(N \log 10^9 + Q \log 10^9)

It is even possible to perform binary search instead of linear search in solution 2 to achieve a complexity of \mathcal{O}(N \log 10^9 + Q \log \log 10^9).


There are no comments at the moment.