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

×

curious to know the solution for chef and prime queries

Can any one share any simple approach for the problem chef and prime queries in in the June challenge

chef and prime queries

asked 12 Jun '17, 15:39

vivek_reddy's gravatar image

4★vivek_reddy
615
accept rate: 0%

edited 12 Jun '17, 15:41

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

(12 Jun '17, 15:44) vivek962★

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

(12 Jun '17, 15:51) vivek_reddy4★

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 https://codelikepros.blogspot.in/2017/06/solving-codechef-june-long-challenge.html

(12 Jun '17, 17:36) hulk_baba4★

awesome !!

(12 Jun '17, 18:46) vivek_reddy4★

This question took a long while and a lot of WA/TLE to solve.

Here's my approach without using trees:

  1. Since X and Y can be a maximum of 10^6, we seive till 10^6 to mark the prime numbers.
  2. Prime factorize every number and store it contigiously in an array, while keeping the index of start of each number in another array.
  3. Divide the entire array into root(n) blocks each of (n) elements.
  4. For each block, calculate the number of each primes (1 to 10^6) and store it as sum in a 2D array with row denoting the block number and columns denoting each prime (2,3,5...)
  5. For every input L R X Y, find the first prime after X and the last prime before Y.
  6. Find the number of blocks that completely lie inside L and R.
  7. Use the following to determine the number of primes between X and Y in the range Block after L to block before R by using the 2D array generated earlier.
  8. For the elements before the first block and after the last block, just iterate through the prime factorization and increment ans if prime is between X and Y (at max root(n) operations.

Here is the link to my solution: https://www.codechef.com/viewsolution/14155947

link

answered 12 Jun '17, 15:51

abdullah768's gravatar image

6★abdullah768
2.4k420
accept rate: 17%

edited 12 Jun '17, 15:54

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

(12 Jun '17, 16:01) vivek_reddy4★

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.

(12 Jun '17, 16:05) abdullah7686★

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

(12 Jun '17, 16:59) likecs6★

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 ?

(12 Jun '17, 17:05) vidit_1231★

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

link

answered 12 Jun '17, 16:56

likecs's gravatar image

6★likecs
3.7k2078
accept rate: 9%

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.

link

answered 12 Jun '17, 17:39

hulk_baba's gravatar image

4★hulk_baba
939
accept rate: 0%

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.

link

answered 13 Jun '17, 13:02

vg_codechef's gravatar image

4★vg_codechef
112
accept rate: 0%

edited 13 Jun '17, 13:03

Great analogy :)

(13 Jun '17, 14:30) lohit_974★

You can use a Persistent Segment Tree to store the sum of exponents of Primes. And then for every array element upgrade the Tree with the new sum of exponents.

Your answer would be query(version[r])-query(version[l-1]), taking version[0] to be completely empty.

link

answered 12 Jun '17, 15:48

trijeet's gravatar image

6★trijeet
2355
accept rate: 25%

I generated all prime numbers till 10^6.

I took each prime number and found out how many of its multiples exist in the array. in the given example 2 3 4 5 is the array and first prime number is 2 so at each of the indices that contains a multiple of 2 add the exponent(to an empty array initially)

given array:2 3 4 5

initially: 0 0 0 0- state 0

for 2 the array becomes : 1 0 2 0- state 1

then for 3: 1 1 2 0-state 2

for 5: 1 1 2 1-state 3

each of these is a state so for l,r,x,y such as 1 3 2 3 the answer is sum of numbers from 1 to 3 in state 2 minus that in state 0. I was stuck here then I saw Gaurav sen's video on persistent segment trees and got the answer in the required time.

link

answered 12 Jun '17, 15:51

simha's gravatar image

4★simha
1515
accept rate: 0%

edited 12 Jun '17, 15:53

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

link

answered 12 Jun '17, 16:04

sdssudhu's gravatar image

6★sdssudhu
1.0k310
accept rate: 15%

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

please help me out!

link

answered 12 Jun '17, 16:47

vivek4434's gravatar image

1★vivek4434
111
accept rate: 0%

@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

(12 Jun '17, 19:08) hulk_baba4★

Tell me where you find difficulty to understand code?

(12 Jun '17, 20:39) vivek44341★

Hey, you can use Merge Sort segment tree.

link

answered 12 Jun '17, 17:46

vikasmaurya's gravatar image

5★vikasmaurya
111
accept rate: 0%

yes,with a modified merge logic

(12 Jun '17, 17:47) vidit_1231★

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

link

answered 12 Jun '17, 18:23

sidd845's gravatar image

3★sidd845
254
accept rate: 0%

@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?

link

answered 14 Jun '17, 04:11

ps_1234's gravatar image

4★ps_1234
593
accept rate: 0%

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,240
×230

question asked: 12 Jun '17, 15:39

question was seen: 1,601 times

last updated: 14 Jun '17, 04:11