DIVMAC - Editorial

editorial
, , , ,
21

can someone please tell me why i m getting TLE -> https://www.codechef.com/viewsolution/11535913

22

I made a test case for this problem, below is the generator of the test case. Its pretty self explanatory of how I go on to generate the test case. In the question it was given that sum of M over all test cases is <= 10^6. So I have kept T = 10 and M = 10^5.

All the numbers i.e. A[i] 's are 10^6, which is again within the constraint of the problem. But this seems to give TLE for my own code which got AC during the contest. Here is the link for the AC Solution of mine. It takes about 7 seconds to run on my mac machine.

import random
T = 10
N = 10**5
M = 10**5
print T
for _ in xrange (T):
	print N,M
	for __ in xrange (N):
		print 10**6,
	print
	for ___ in xrange (M):
		L = random.randint (1,N)
		R = random.randint (L,N)
		typ = random.randint (0,1)
		print typ,L,R
23

Can someone please explain why my solution is giving TLE on 2 Cases. I have followed the exactly same method explained in tutorial.

https://www.codechef.com/viewsolution/11790577

24

Can some body please prove how the time complexity of the algorithm got reduced form O(Q N lgN) to O(N lgM lgN + Q lgN), where N is the size of the array, M is the bound on the elements of the array, and Q is the number of queries, by adding count_non_degenerate field to every node of the segment tree?

I have an intuition about the idea that we won’t go into subtree rooted at node x if x has count_non_degenerate=0, which will reduce the time , but I cannot quantify it . Can somebody please help ?
@dpraveen

25

@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)).

26

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.

27

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

28

anyone pls?