Editorial for COCI '22 Contest 5 #3 Logaritam

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.

Since a_{1 \cdot 1} = a_1+a_1, a_1 has to be equal to 0, so if the first element is changed the sequence cannot become logarithmic again. It is easily shown that a_{xy} = a_x+a_y for every pair of positive integers x, y is equivalent to a_m = \alpha_1 a_{p_1} + \alpha_2 a_{p_2} + \dots + \alpha_k a_{p_k} for positive integer m = p_1^{\alpha_1} \dots p_k^{\alpha_k}. We conclude that logarithmic sequence is uniquely defined by values at prime indices. If the index p of changed element is prime one possible way to "fix" the sequence is to change all of the elements at indices which are multiples of p, there are \lfloor \frac n p \rfloor-1 of them. If that is the minimal number of changes necessary, then for any index x of changed element the minimal number of changes necessary will be \lfloor \frac{n}{\text{greatest prime factor of }x} \rfloor-1 (since it is necessary to change at least one prime factor of x).

We will prove that is the solution and we can implement it with standard algorithm for finding prime factorization in \mathcal O(q \sqrt n).

Proof: Using induction by n let's prove a stronger claim for odd primes p: "Changing multiples of p is the only minimal solution".

If n is not divisible by p the number of changes stays the same and the solution is unique.

If n is divisible by p then clearly the solution for n-1 needs to be expanded by changing the n-th element and we get that \lfloor \frac n p \rfloor-1 is the least number of changes. Assuming that there exists another minimal solution that solution doesn't change the n-th element and it is necessary to change another odd prime index q (for q = 2 it can be seperately shown it requires more than minimal changes) for which by induction hypothesis has unique solution for first n- element. Since 2q is not divisible by p that solution would have at least \lfloor \frac n p \rfloor changes so it is not minimal.

For p = 2 it doesn't necessarily hold that minimal solution is unique (for prime \frac n 3 < q \le \frac n 2 it is possible to change q instead of 2q), however it still holds that the minimal number of changes necessary is \lfloor \frac n 2 \rfloor-1. The proof similar to the previous is left for the reader as exercise as well as finding implementation which runs in time complexity of \mathcal O(n+q).


There are no comments at the moment.