×

PRIMECLO - Editorial

Author: Teja Vardhan Reddy
Tester: Aswin Ashok
Editorialist: Aswin Ashok

MEDIUM

PREREQUISITES:

Segment Tree, Segmented Sieve or Rabin Miller Primality Test, Prime Gap

PROBLEM:

You are given an array a (1 indexed)of size n. You have to process following operations on the array

1 l r : update elements of indices from l to r inclusive to difference of element and nearest strictly smaller prime (eg: 5 gets updated to 5-3=2). Also note that since 0,1,2 does not have primes below then even after update they remain the same.

2 l r : Find Sum of elements of array from l to r indices

EXPLANATION:

After first update each updated element becomes less than 2000 since the prime gap is less than 2000 for given range of input.
Since in the constraints it is given that the difference between the Max and Min of array a is less than $10^5+200$. So we can find all primes in the range $[Min_a,Max_a]$ using segmented Sieve or Rabin Miller and store it in an array.
We can also find and store the nearest smaller prime for each number in the range $[3,2000]$
Now we have to maintain two segment trees one with sum and other one with Maximum value of the range.

When we are updating if the leaf node in the segment tree is greater than 2000 we can do a binary search in array of primes to find the next smaller prime but if the leaf node is less than 2000 we already we know its nearest smaller prime. Once the nearest smaller prime is found update the leaf node and the nodes above. One thing to note is that we need not update the elements less than three so if the maximum element of range is 3 we need not update it at all

To find the sum we can directly query on sum segment tree.

SOLUTIONS:

Solution can be found here.

This question is marked "community wiki".

143
accept rate: 0%

19.8k350498541

 0 Hello,I am a school student , the maths requried for LOC is of a bit high level. I would be grateful if u all can suggest tutorials or books from which I can study:)@aswinashok44 @teja349 answered 01 Jul '18, 18:43 104●7 accept rate: 2% Hello Krish, LoC has become a little harder over the past two years. We are trying to find the correct difficulty for school students. Hope the last session was easier. I would suggest you to practice hard and learn from online forums like this, codechef and codeforces blogs are a good source of information. (06 Jul '18, 13:29) Yep the last session was easier:) But finding proper material to pratice from is though.Can u plz suggest the list of books or websites specifically . Even for MATHS. Thanks in advance. (09 Jul '18, 23:27) @aswinashok44 (02 Aug '18, 22:33)
 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:

×15,852
×1,768
×199
×23
×22
×16

question asked: 02 Jun '18, 21:24

question was seen: 587 times

last updated: 02 Aug '18, 22:33