DIVMAC - Editorial

Can someone tell me why is this solution giving runtime error–>solution ?

1 Like

Guyz i got RTE for this problem inspite of it working well on ideone for the sample test cases as well as on codeblocks. Please help me with it. Here’s the link to my solution https://www.codechef.com/viewsolution/11528652

I used the following techniques:

  1. Update: If any node of segement tree has 1, then we don’t need to update the left and right subtrees because all elements in subtrees will be equal to 1, and any update will not make any difference.

  2. Query: If any node of segement tree has 1, then we don’t need to go any further down, because all elements in subtree of that will be equal to 1, and maximum is 1.

And just 2 simple if statements made a big difference from TLE to 0.14s

https://www.codechef.com/viewsolution/11418957-TLE

https://www.codechef.com/viewsolution/11421332-100points

7 Likes

Each number from 1 to 10^6 has number of factors at most 19. Hence, each node in the tree can only be updated at most 19 times (bounded by a smallest coefficient. So the worst case for the combined complexity of all updates is an order of 19 * N steps which is still O(N). All queries can be solved in O(logn) because we are using segment tree.

I solved this using basic segment tree. Notce that each number from 1 to 10^6 has number of prime factors (including repitition) at most log2(10^6) ~ 19. Hence, each node in the tree can only be updated at most 19 times (ie. bounded by a smallest coefficient). So the worst case for the combined complexity of all updates is an order of 19 * N steps which is still O(N). To ensure this, we must ofcourse avoid down propagation during update when a tree no longer needs update (ie. when the max factor for a subtree is already 1). All queries can be solved in O(logn) because we are using segment tree.

To update a leaf, you can preprocess the prime factorization of each number from 1 to 10^6 using sieve. (preprocessing took .7-.8 s on my laptop).

Solution: CodeChef: Practical coding for everyone

What about T test cases, isn’t the complexity then O(|T||N|log|MAX|log|N|) which shouldn’t pass???

When I saw the problem in the first time I was confused by constraints T=100 and N=10^5 without any extra constraints for a sum of N in a single file. After a long time of thinking I thought there is something strange here. So I decided to check out the real constraint for a sum of N and realized it is exactly 5*10^5. So what is the reason for not publishing the real limits?

1 Like

can someone please tell me why i m getting TLE → CodeChef: Practical coding for everyone

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

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

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

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

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

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
ios_base::sync_with_stdio(false);
cin.tie(NULL);