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

×

GGSPAG - Editorial

PROBLEM LINK:

Practice Contest

Author: Suraj Kumar Tester: Rishabh Gupta Editorialist: Suraj Kumar

DIFFICULTY:

MEDIUM

PREREQUISITES:

Data Structure, Segment tree, Sieve of Eratothenes

PROBLEM:

You are given an array of N inegers on which you have to perform Q queries which can be of update type in which you need to change the content at index i with X. The other type of query is to count the total number of primes between a given range of indices L and R.

QUICK EXPLANATION:

Find an efficient way to tell the no. of prime numbers between two given indices of an Array.

EXPLANATION:

The problem is pretty straightforward. First of all we need to find all the prime numbers from 1 to 100000, which can be done using the sieve. After this is done we need to build the segment tree, which can be done in order of nlogn. After the tree is built we simply need to query the tree for each of the query of first type in order of logn. For the update query we need to change only those part of the tree which will be affected by this update. This can also be done in logn.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here. Tester's solution can be found here.

RELATED PROBLEMS:

asked 24 Jan '17, 18:59

surajumang08's gravatar image

3★surajumang08
5
accept rate: 0%

edited 25 Jan '17, 14:10

admin's gravatar image

0★admin ♦♦
19.8k350498541

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,755
×1,672
×301
×48
×1

question asked: 24 Jan '17, 18:59

question was seen: 593 times

last updated: 25 Jan '17, 14:10