DIVMAC - Editorial

@shubamg First see the point that an element can be divided only log(n) times cause after that it becomes 1.

So how I approached this problem is to first maintain a range I calculate largest smallest prime factor and maintain it in a segment tree. Now perform point updates on all points on ranges. However don’t go inside segments which have the largest smallest prime factor as 1 as you cannot do any operation for 1.

Now you notice that each range can be called atmost logm times and there are nlogn ranges.So it is O(Nlog(m)log(n)). For each query it is log(n). So the extra Qlogn factor.

So it is O(Nlog(m)log(n)+Qlog(n)).

I would like to give a proof of time complexity of the algorithm stated in the editorial. I had a doubt earlier that there may be updates on the ranges which have all their members equal to 1. This will not decrease the value of any array element but still consume extra time. But we can still use amortised analysis to prove the time complexity of the algorithm.

So let the processing at any node of the segment tree may take at max \alpha time. Consider the potential function \phi = 2*\alpha*\sum_{n \in \textrm{node}} \sum_{i=l(n)}^{r(n)} f(A[i]). Here n can be any node of segment tree which covers range [l(n),r(n)]. f(x) gives number of prime factors of x e.g. f(2^n)=n, f(6)=2.

Using this \phi, we can prove the desired time complexity of the algorithm.

Can someone please explain why I am getting TLE, I did exactly what the editorial said TLE Solution Link. @vijju123, @likecs, anyone? please help

I think he is updating lazily in Klog(K) where K is the size of the lazy marked segment. Also atmost the complexity would be 20Nlog(N)

Increase the size of your segment tree and other arrays accordingly! You are trying to access an element which is more than size of the arrays you have made.

@lohit_97 then y am i not getting 10 points? My code is sufficient for the 1st two subtasks.

My solution is similar to your first map approach :


Difference is i am not using a map,

i am maintaing an array ,

next[i] = index of the the next number to the right which is not 1 ,

next[i] = (A[i+1] == 1) next[i+1]:i+1

In this way updating next pointer is O(1)

we have pointer to next element which is not 1

yes after atmost 19 times a particular element is gaurenteed to be 1

anyone pls?

try to use