×

DIVMAC - Editorial

Author: Kirill
Tester: Praveen Dhinwa
Editorialist: Ajay K. Verma

Medium

PROBLEM:

Given an array of numbers A, support the following two queries: 1) for a given range [L, R], reduce each number in A[L..R] by its smallest prime factor, 2) for a given range [L, R], find the number in A[L..R] with largest smallest prime factor.

QUICK EXPLANATION:

Use a segment tree while maintaining the segments in which each number is equal to one.

EXPLANATION:

We are given an array A of size N, and we are supposed to maintain two kind of range queries on this array: 1) Update the numbers in a range A[L..R]. 2) Query some information about the numbers in the range A[L..R].

Let us first solve a simpler version of the problem, in which we support the following queries, and then we will come back to the original problem: 1) Update a number A[x] 2) Query some information about the numbers in the range A[L..R].

This seems like a classical segment tree problem. We can create a segment tree for the array. As explained here in the segment tree each node maintains some information about the elements A[k * 2^x, (k + 1) * 2^x). In our case, this information would be the largest smallest prime factor of the numbers in the range.

struct info {
// The node corresponds to A[low..high]
int low;
int high;

// The largest value of the smallest prime factors
// of the number in A[low..high].
int value;

// The children nodes of this node containing
// [low, mid], and [mid + 1, high].
info* left;
info* right;
};


Once we update a number A[x], the information in all nodes containing the index x will be updated. There are at most O (lg N) such nodes, hence the update operation can be done in O (lg N) time. For the query operation about the range [L, R], we find the list of nodes whose ranges is contained in [L, R], and take the maximum of their values. Once again, there are O (lg N) such nodes, hence the query operation can also be implemented in O (lg N) time. For the implementation details of update and query, please see here.

Now, let us see how we could solve the original problem. One possibility could be that, when we get the range modification entry, we modify each element in the range one by one, and hence perform (R - L + 1) single element update queries. This approach would be to slow, as it makes the complexity of range update query to O ((R - L + 1) lg N). Next, we discuss that many of these single element update queries can be ignored, and the number of actual performed queries is much lower.

Note that, if the value of an element A[x] is 1, then update query on A[x] does not have any effect on the segment tree. We call such queries as degenerate queries, and can discard them. Also note that a number M can be written as a product of at most O (lg M) prime numbers, Hence, we can perform at most O (lg M) non-degenerate modification queries on A[x] = M, all the latter queries will be degenerate. This means that if all numbers in the array are smaller than M, then a most O (N lg M) non-degenerate single element update queries would be performed. Each single element update query takes O (lg N) time, and hence all update queries can be performed in O (N lg M lg N) time.

However, now the problem is how to find the non-degenerate single element update queries for the range [L, R]. For this purpose, we maintain another information in the segment tree node, which is the number of elements in the range which are larger than one.

The following snippet shows how to use this information so that we only perform single element update queries, without iterating through all elements in the range. The idea is similar to the lazy propagation.

struct info {
// The node corresponds to A[low..high]
int low;
int high;

// Number of elements in A[low..high], which are larger than 1.
int count_non_degenerate;

// The largest value of the smallest prime factors
// of the number in A[low..high].
int value;

// The children nodes of this node containing
// [low, mid], and [mid + 1, high].
info* left;
info* right;
};


Now, while performing the range modification query, we can discard all subranges which have all elements equal to one.

void update (info* nd, int L, int R) {
// This node has a range disjoint with [L, R]
if (nd->low > R || L > nd->high) continue;

// All elements in this range are 1, nothing to do.
if (nd->count_non_degenerate == 0) continue;

if (nd->low == nd->high) {
// Perform the single element update query
...
return;
}

update(nd->left, L, R);
update(nd->right, L, R);
}


This means all the range update queries can be performed in O (N lg M lg N), while the range query time is O (lg N) per range.

TIME COMPLEXITY:

O (N lg M lg N + Q lg N), 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.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution
Tester's solution will be uploaded soon.

This question is marked "community wiki".

6★djdolls
2.2k508484
accept rate: 0%

19.0k348495533

 9 I think that test cases were possibly weak, because they allow the following approach to pass (if there were a lot of queries with not many updates, then I expect it to fail). First, for each possible input value, compute its smallest prime factor. This can be done using Sieve for example. This is pretty standard. Then, the crucial observation is that every initial value in the array can be updated at most 19 times. This is true because $A[i] \leq 10^6$, and the number with the most prime divisors in this range is $2^{19}$, so it can be divided by it's smallest prime factor $19$ times until it becomes $1$. Notice that as soon as the number becomes $1$, we don't have to care about it at all: first, update operation on $1$ doesn't change its value, moreover, it doesn't have any affect on the result of any query operation, because its result is guarantee to be at least $1$. Based on the above observation, the following solution is possible. Maintain a map $S$ of positions in the array to their value. For example, if $A = [2,3,1,5]$ then $S[1] = 2$, $S[2] = 3$, $S[3] = 1$ and $S[4] = 5$. Then, for each $update(L, R)$ use binary search (lower_bound in C++ can be used) to find the first key in $S$ greater or equal to $L$ and go through keys from this position to at most $R$ dividing each value by its smallest prime divisors. As soon as any of these values becomes $1$, delete it from the map $S$. It follows that each input number can participate in queries at most $19$ times which is nice fact. Query operation is performed analogously. For $query(L, R)$ use binary search (lower_bound in C++ can be used) to find the first key in $S$ greater or equal to $L$. Then go through all keys from the found key to at most $R$, actualizing the result by considering the smallest prime factor of the current number. So the query operation has time complexity O(|S| + log(|S|)) and if no 1's get deleted during update operations, then a single query will have O(N) time complexity, which is a lot. My submission using exactly the above idea is available here However, this approach can be easily transformed to a more efficient one using the same idea (any input number will participate in at most $19$ updates) by using a segment tree rather than a map, which will be probably almost the same as described in the editorial. answered 15 Sep '16, 15:46 734●8●43●90 accept rate: 12% 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 (15 Sep '16, 20:31)
 7 I used the following techniques: 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. 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 answered 15 Sep '16, 18:49 1.1k●1●10 accept rate: 10%
 2 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? answered 15 Sep '16, 20:29 6★kefaa 11●2●8 accept rate: 0%
 1 Can someone tell me why is this solution giving runtime error-->solution ? answered 15 Sep '16, 17:43 21●2 accept rate: 0%
 0 Can someone how did this solution based on lazy propagation work? ( https://www.codechef.com/viewsolution/11417075 ) answered 15 Sep '16, 15:20 6★likecs 3.5k●13●61 accept rate: 9% 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) (15 Sep '16, 15:33) apptica6★
 0 practice is linked to contest page only... answered 15 Sep '16, 15:36 11●1 accept rate: 0%
 0 The Practice Question Link is pointing to the Contest Page. The tester solution's link need to be updated as well. Please Update the links. answered 15 Sep '16, 15:54 187●1●7 accept rate: 0%
 0 @pkacprzak i also did the same solution. IO optimizations got it passed answered 15 Sep '16, 15:58 6★apptica 909●2●10 accept rate: 17%
 0 Well, just to say, One need not maintain the number of ones in range L-R of a node. Look at my solution here to understand more clearly. I have used almost everything similar to what is mentioned in the editorial, and the fact that if a node of segment tree is "1", I need not propagate down, as all its child elements will be also 1, since each node is storing the max. answered 15 Sep '16, 16:29 4★lohit_97 320●8 accept rate: 2%
 0 I used Segment Tree with Lazy Propagation, while maintaining a vector of all prime divisors in decreasing order. This concept was quite obvious, and the solution worked flawlessly. Here is the solution: here answered 15 Sep '16, 16:43 11 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×14,464
×2,412
×1,580
×128
×15

question asked: 15 Sep '16, 14:56

question was seen: 9,829 times

last updated: 16 Nov '17, 21:01