PRMQ - Online solution June 17 (unofficial)

editorial
, , , ,
1

Problem Link

Contset Link

Practice Link

Prerequisites

Prime Factorization, Binary Search, Segment Tree/ Merge Sort Tree

Quick Overview

Given N numbers and Q queries, for each query find sum of number of prime numbers which are between X to Y (both inclusive) in prime factorization of numbers from L to R (both inclusive).

Solution

As this is not official editorial i directly jump to full solution. for subtask 1 brute force should pass, for second subtask my sqrt solution gets 30 points linked below.

100 points

The idea is to use Segment Tree pretty much like standard one but with few modifications. Like in normal Segment Tree for sum queries, in each node we store sum of numbers for range represented by the node, here we store prime numbers in prime factorization of numbers represented by range of that node and also maintain count of prime numbers.

For fast queries using binary search we store it in sorted order and calculate prefix sum for each node later.

Building the Segment tree:

Let’s start with leaf nodes which represent one number, as stated above we store primes in it’s factorization and their count in sorted order let say we store in an array then it’s maximum size can be 8 as 21 * 3 1 * 51 * 71 * 111 * 131 * 171 * 191 > Max(a[i]).

Now we build inner nodes, they just contain primes in list of their sons. which is like merging list of sons into one. let’s find length of list contained in these nodes let it represents range of length L also for worst case let no prime factor is common among those elements so max length can be 8 * L as each may have at most 8 prime factors.

check build function for details

complexity analysis: O(NlgN)

merging 2 lists of length O(L/2) takes O(L) time.

at level 1, 1 node of length N => take O(N) time.

at level 2, 2 nodes of length N/2 => 2 * O(N/2) = N

…

…

at last level N node of length 1 => N * O(1) = N

summing at each level gives total O(NlgN) time complexity for building.

similarly

Memory complexity: O(NlgN)

Query:

Let say we have query L, R, X, Y as given in problem. It’s same as normal one except one modification, from each node that is queried we want sum of count of primes between Y to X, binary search is used here.

check query function.

complexity: O(lg2N)

Code:

Sqrt solution


(https://www.codechef.com/viewsolution/14145975) for subtask 1 and 2.

Segment Tree/Merge Sort Tree like

(https://www.codechef.com/viewsolution/14243341) full solution.

this is my first blog post feel free to ask in comments

1 Like
2

can anyone please upvote my comment, i need to ask question but unable to do so because of low karma points…

4 Likes
3

There is a separate thread for users like you to ask questions. Ask there. Also, upvotes wil not give you karma for this answer.

4

what will the space complexity be , for the segment tree approach?

1 Like
5

nice work!! one can also follow this thread https://discuss.codechef.com/questions/101349/prmq-june-17-unofficial-editorial.

1 Like
6

a node contains distinct primes in factorization of numbers occurring in it’s range and one element can have at most 8 distinct prime factors, let say all have distinct prime factors so size of node can be 8 times the length it represents. so u can sum them at each level which will be 8 * N, and there are logN levels. so O(NlogN).

7

we store the list of primes for all numbers in the range of a given node in segment tree, i.e we can say that we store list of prime factors(including counts) of product of numbers in the range of a particular node ,so for the root node whose range = (1:n) , the list size can be O(n) right ? So in that case the overall space complexity can be O(n^2) ? please correct me if i’m wrong.

8

note that there are logN levels. now let root i.e node 1 is at level 1 so it needs 1 * O(N) space. at level 2 there are 2 nodes so need 2 * O(N/2) = O(N) space. at level 3 there are 4 nodes => 4 * O(N/4) … LogN times. at last level N * O(1) = O(N).

hope this one helps

9

Why the

build

function is O(N lg N)? The merge part itself would keep merging two list which at worst case has no intersection at all, the merge part thus will getting heavier when it is more near to the root, am I wrong?

10

i have added complexity analysis pls check again.

1 Like
11

Here is my approach:

  • For subtask 1 and 2, it is easy to construct a 2D prefix sum table with rows as prime factors and columns as 1..N. There are 78,498 primes less than 10^6 so the size of table is around 78,498*N. Construct the table can be done in O(N*78498*log(a[i])) while querying takes O(1) complexity. As N\leq 1000, it is efficient enough.

  • For subtask 3, N is quite large so we will take the observation like this: Each number a[i] will contain at most one prime factor larger than 10^3. Because if it contains at least two prime factors larger than 10^3, it must be larger than 10^6 which exceeds the constraint. From this observation, we will construct a 2D prefix sum table like in subtask 2 , but now only with 168 rows and N columns (since there are only 168 primes \leq 10^3). We will use this table for answering queries with factors \leq 10^3 in O(1) like above subtask. How about those queries with factors > 10^3? From now we will call them large factors. Each a[i] is now specified by only a large factor, for example array a = [5,2018, 6033, 2011], we will convert it to array b = [0, 1009, 2011, 2011], if a[i] does not have a large factor, b[i] equals to 0, otherwise b[i] equals to the large prime factor of a[i]. Done! A query f(L,R,X,Y) with X,Y > 10^3 now can be easily answered if we consider it is equivalent to get(L,R,X-1)-get(L,R,Y) where get(L,R,X) counts how many numbers in segment [L..R] of array b that is strictly greater than X. This is the same as problem KQUERYO on SPOJ http://www.spoj.com/problems/KQUERYO/. I used Segment Tree for online solution.

1 Like
12

You are assuming that all prime factors of the numbers will be distinct, but that is not necessary, so in worst case, each number can actually have 19 factors when the number A[i] = 2^19. For a number X, it can have at maximum log(X) to the base 2 factors.
So, now coming to complexity of build function, each base node(leaf node) can have at maximum 19 factors. Lets say all ‘N’ leaf nodes have log(A[i]) factors, so at each level there would be Nlog(A[i]) numbers, and there are logN levels, so build function complexity happens to be
Nlog(N)*log(max(A[i])) which is good enough to run within the time complexity :slight_smile:
I hope this helps the readers to understand the complexity better.

1 Like
13

Thanks @abhi1shek1 for your solution !!

14

I used sqrt decomposition by storing the 1-D prefix sum for each block (78500-items per block).
A separate array for the factorization into (prime_index, exponent) pairs.
And finally a third array from prime => prime_index

To compute an answer for (L, R, X, Y), start by translating X => X_index (same for Y).
Then for the O(sqrt(n)) values that fall outside of a precomputed block, we just brute force the sums. Because there are at most 7 primes in a factorization, this is O(sqrt(n)) with a small constant.
For the sqrt blocks, having the full array allows for O(1) computation per block using the precomputed prefix sums for an overall O(sqrt(n)) run time per query.

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

1 Like
15

how do you wish to get karma points from a answer marked as community wiki? remove that.

1 Like
16

I could not come up with a good memory complexity using sqrt during contest.
@pabloaguilar thanks for sharing your solution.

17

hey @abhi1shek thanks for your solution.I implemented it but got only 30 points plz check my solution https://www.codechef.com/viewsolution/14268547

18

can anyone tell if why my solution is not working…here

In a node,i have stored vector of pair where first is prime factor and second is the power.

struct node{
    vector<pair<int,int> >pr;
    int size;
};

i have submitted it around 35 times but no luck.Please help me.