PRMQ June 17 Unofficial Editorial

general
,
1

Hey all, This problem can be solved using just segment tree, I have written a blog which explains my solution, you can visit it Here.

1 Like
2

You can also use STL to shorten your code. My code using same approach

1 Like
3

Hey thanks for the explanantion but could anyone please give the approach for this problem using square root decomposition? I don’t karma points to ask one, so am posting it here. I have tried using square root decomposition to solve this problem and am doing it in O(q*sqrt(n)*log(sqrt(n)) ) but am getting TLE for all cases in the last subtask. Here is my solution https://www.codechef.com/viewsolution/14214707. Any help would be welcome. Thanks!

1 Like
4

Thank u for the link @hulk_baba

1 Like
5

I want some segment tree problems with different senarious like June contest it gave 4 variable related PRIMEQ problem I know it is segment tree problem But I actually not understood what to put in the node…Help me…

6

@divyansh_gaba7 could you please explain your code

7

I’ve tried using BIT and MO’s but got two tles in last subtask nice solution @hulk_baba
can somebody plz post links to questions similiar like this?
where we have to made our own custom segment trees.

8

This problem has a pretty neat and straightforward solution if u process the queries offline. Observe that

F(L,R,X,Y) = F(1,R,X,Y) - F(1,L-1,X,Y)

So, first, we input all the queries together. Then we divide each query into 2 queries of type F(1,S,X,Y) and then sort these queries on S. After that, its simple point update range query which can be easily done with a BIT(or segment tree).

You can refer my solution here
.

9
  • Basic Idea
  • In a sorted array for X and Y we can use binary search to find the size of the interval is result with prime factors in the range of X and Y.
  • Ex we have sorted array of prime factors (0 base array)2,2,5,5,5,11,11,23. Now query is for X=3,Y=14. Then index will be found using upper_bound and lower_bound. upper_bound-1 for right hand of the interval with search for Y , similarly lower_bound for the left hand of the interval with search for X.
  • For above upperbound-1 = 6 , lowerbound = 2. Interval Size = 5.
  • Solution
  • We will be using above basic idea and segment tree
  • Our Leaf Node will be containing the prime factorization of the number in a sorted manner.
  • For the process of merging two nodes here they are basically two sorted array we will use the idea of merging two sorted array from the MergeSort.
  • Then the result will be calculated in the similar manner using binary search for the interval size as shown in basic idea and segment tree.
  • My Submission Uncomment the cout statements for better understanding
  • Codeforces Blog for Segment tree Implementation
10

I have a question, I don’t know why but for me, just for computing the prime factors for each of the numbers took 0.4 seconds, as seen in here,link, can anyone tell me what I was doing wrong here? I am not even doing anything for the queries, the time for computing the primes itself is 0.4 seconds.

11

@yash_22 thank you.

12

You can refer it here

13

Thanks a lot man! I still have a doubt. Shouldn’t 78500*250 give MLE for static arrays? I assumed that i would get an MLE and broke the problem into primes less than 1000 and greater than 1000 to overcome the issue.
Btw just created the array for all primes in a block and am getting AC. Wish I had tried this during the contest. Thanks again man! Here’s my solution CodeChef: Practical coding for everyone
PS: I really want to upvote your answer but don’t have enough reputation points to even upvote it.

1 Like