You are not logged in. Please login at www.codechef.com to post your questions!

×

DIVMAC Editorial (Unofficial)

6
1

Here is the Link for the problem for those who are just surfing the forum randomly ;)

DIFFICULTY   Easy-Medium

PRE-REQUISITE
1) Segment Tree    2) Sieve of Eratosthenes

PROBLEM:
Given an array A of N positive integers, we are expected to perform two type of queries GET and UPDATE, description of these queries are given in the problem.

EXPLANATION   We are required to use LeastPrimeDivisor(x)[LPD] in both of our queries, so a pre-processing step can be to evaluate and store LPD of all the Ai's in an array, say Sieve[], Since |Ai| <= 10^6

if (you are new to sieve):

Sieve

If (you are new to RMQ and Segment tree):

Topcoder Tutorial
Hackerearth Tutorial
RMQSQ SPOJ

GET(L,R)

query asks us to return the maximum of LPD of all Ai in range [L, R], equivalently its a Range-Max query which can be done using segment tree where each internal node of segment tree holds the maximum of LPD of its two children. So first build a segment tree which support range-max query and return max(LPD) . Since we already have LPD for all element in sieve, this step isn't much of an issue. see code for more clarification.GET(L, R) takes O(logN) time per call as usual.

UPDATE(L, R)

As you can expect is our Range-Update query,  seeing range updates we might be tempted to use lazy propagation at first, but thinking carefully, we can notice that lazy terms provides no useful information on how to update a node's for its maximum value of LPD. So we are better with point updates.But the problem with point updates is they take O(logn) per call, and calls in our worst case can be N for UPDATE(1, N)naively, doing point updation on this range would give O(NlogN) time per query or equivalently O(M*NlogN) = O(N^2logN) for M of such queries, which will certainly time out.

OBSERVATION

If you watch closely, each element in the range [L, R] of the array A is being reduced by a factor of its LPD, also after an element is reduced to 1 it remains 1 forever. the limit for an element in our case is 10^6 which is roughly 2^20, Thus we are assured that each of our element would become 1 after going through at max 20 updates(convince yourself). Thus we can stop updating those element which are already reduced to 1, so our worst case time complexity for M UPDATE(1, N) queries reduces to O(20*NlogN)(independent of M)

ANALYSIS

Pre-Processing time in sieving : O(NloglogN)
building segment tree : O(4N) ~ O(N)
GET(L, R) : O(log(N))
UPDATE(L, R) : O(20
NlogN)
Total Time Complexity : O(NloglogN + N + MlogN + 20*NlogN) ~ O((M+N)logN)

A similar question that you can try is GSS4 SPOJ this is a classical SPOJ problem and nearly everyone who has ever got to know about segment tree knows about it, so you can easily guess why there were so much of AC's for that problem.

My Solution

NOTE

Actually in practice the update operation can be much faster than O(20*NlogN). if you implement UPDATE(L, R) operation by doing naive point update over the range(L, R) then surely its going to take O(NlogN) time per operation but if you implement UPDATE function like the one to BUILD the segment tree then each UPDATE(L, R) will take O(R-L+1) time, if R-L+1 dominates logN, otherwise it would be logN. Our worst case would be the same as all the query can be of type UPDATE(L, L)(here logN dominates R-L+1 term) in which case the operation will take O(logN) time, same as naive point update, comment if you need more on this.In the analysis, to make thing worst for us i assumed all the queries are of GET type and we still account for all the possible UPDATE operations.

asked 15 Sep '16, 15:15

ashwanigautam's gravatar image

3★ashwanigautam
187111
accept rate: 0%

edited 15 Sep '16, 21:34

The official editorial is quite great, do read that :)

(15 Sep '16, 15:16) ashwanigautam3★

@ashwanigautam I didn't use Seg Tree , still got an AC.

Although, I used the idea that after certain(max. 20) number of updates any number would become 1 and stay 1 forever so it is useless to traverse that position in update or get operation. I used 2 extra arrays to store and jump to next number which is not 1.

Here is the link to the AC solution.

Nice editorial by the way. Cheers mate.

link

answered 18 Sep '16, 01:19

vikasj554's gravatar image

4★vikasj554
2197
accept rate: 30%

2

yes mate it served the purpose, the memory and time which your code took were somewhat on higher side, you might want to squeeze them in future. Cheers

(18 Sep '16, 16:04) ashwanigautam3★

@ashwanigautam Yes, you're right, my code wasn't very time efficient. I didn't know how to properly implement the Seg-Tree back then. :D I learned it now though. Link to Seg-tree method btw, again, Thanks for the great editorial man. It helped a lot. (Y)

(18 Nov '16, 22:53) vikasj5544★

I did it through, sieve of eratosthenes, I Got TLE is subtask #2 and #3...Optimized a lot, still couldn't pass.

link

answered 15 Sep '16, 17:37

neilit1992's gravatar image

3★neilit1992
1.1k11
accept rate: 20%

Your naive solution is not supposed to pass, although you pre-calculated LeastPrimeDivisors but you query and update takes linear time, which in the worst case leads to quadtatic running time. one way to bring down your running time is using segment tree, i have given links to two awesome tutorial, read them and solve the problem i gave along with them, that would suffice.

(15 Sep '16, 17:47) ashwanigautam3★

In your code instead of Creating a node to check whether update is required or not, you can simply check if(tree[node] == 1), my solution : http://p.ip.fi/nySQ

link

answered 15 Sep '16, 18:32

yougaindra's gravatar image

3★yougaindra
913
accept rate: 0%

oh yes, thanks.. missed this, reduced the program memory to 8.4MB (Y)

(15 Sep '16, 18:34) ashwanigautam3★

I also did the same thing @yougaindra , your solution is very similar to mine.

(18 Sep '16, 09:48) prakhariitd6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,277
×215
×213
×14

question asked: 15 Sep '16, 15:15

question was seen: 1,940 times

last updated: 18 Nov '16, 22:53