curious to know the solution for chef and prime queries

My solution is an offline solution. First prime factorise all the numbers of the array and store it in a vector.

For each index of the array find the starting point of the value in the vector.

Now for a (L,R,X,Y) query we can treat it as number of elements in (L,R)>X - number of elements in(L,R)>Y.

With this information we can do offline pre-processing and solve it using a normal segment tree.

For offline pre-processing we sort all queries and the elements of the segment tree and solve it . See my solution for more details.

Link to my solution

Is there any way to get rid off TLE from my solution [solution][1]

please help me out!
[1]: CodeChef: Practical coding for everyone

Mine solution is a simple one. Just use the sqrt trick for summation between ranges. As in this problem, along with ranges, another query pair (X, Y) is added, maintain prefix sum for it over the sqrt-root ranges. 2 things are needed to be taken care of in this method:

  1. Memory size. Naively is it Max(A_i) * No of Blocks, but it can be compressed to P * No.of.Blocks, where P is number of primes below 10^6.
  2. Choosing an efficient block size would be either of (R, L) pair or (X, Y) pair. My solution timed out for (R, L) pair but passed for (X, Y) pair.

Here is a link to my solution

Extra : This method can also handle point - updates as well and it completely online solution.

Complexity : O(P \sqrt(N) + Q*sqrt(P)), where P is same as above

2 Likes

Hey, This problem can be solved using just segment tree, The approach is we can store the prime factors as key and their count as the value in the leaf nodes of segment tree and we can merge the same keys and add up their count. I have written a blog which explains my solution, have a look here.
Link to the blog.

1 Like

Hey, you can use Merge Sort segment tree.

what we actually store in each node if we use persistent segment trees

We can also view this problem as finding the number of points inside a rectangle.

The points are of the form (X,Y) where X is the index of the number arr[X] in the array and for each X,
Y’s are the Prime factors of arr[X].

The queries are of the form L,R,X,Y which translate to the rectangle formed by x=L,x=R,y=X,y=Y.

So we have points in 2d plane and queries are given by rectangles. we have to find the number of points inside this rectangle(including the border) which can be done by segment trees, Square root decomposition etc.

1 Like

@likecs : P*sqrt(N) exceeds 10^7.I Why doesn’t this give memory limit exceeded? What is the upper bound on the size of the array?

@vivek_reddy can u please explain your approach & code for triplets?

just try to find number of times each unique product term repeats and you need to modular arithmetic

you would have used functions in your solution instead of doing everything in the main() function so that it will be bit easier to understand

I’m sorry, I had not planned to be sharing the code so didn’t bother making it more readable. I was just desperately trying to get an AC.

I have used the same approach, you can see my code for reference here.

Is this approach similar to(In general) maintaining a cumulative frequency of primes then binary searching the indices for x and y ? and doing this thing with either Segment tree/square root decomposition ?

Hey, This problem can be solved using segment tree, I have written a thorough blog on how to solve this problem using segment tree, please visit it here Solving CodeChef June Long Challenge Problem "PRMQ" using Segment Tree

yes,with a modified merge logic

awesome !!

@vivek4434 , it will be useful for the code reviewer if you can provide some comments to explain what you are doing and if possible, use functions

Tell me where you find difficulty to understand code?

Great analogy :slight_smile: