Editorial - Praveen

Problem Name: Praveen and Subsequence

Contest Link: https://www.codechef.com/HACF2018/problems/PRA

Difficulty: EASY

Contest Code: PAR
Prerequisites: AD-HOC

Problem: Praveen went on a date with his girlfriend.He gave her a sequence of numbers from 1 to 1000000. Praveen picked up a subsequence from it and wants his girlfriend to pick a number from that subsequences. What is the probability that the number she picked was a prime number?


The range of the subsequence chosen by Praveen is given which is L and R.
So in this range first we will have to calculate the number of prime numbers.

To calculate the number of prime numbers in a given range the most efficient algorithm is Sieve of Eratosthenes

Now as we have the count of prime numbers , we just have to divide the number of prime numbers present in the range and total numbers in the given range as we can get the probability of choosing a prime number

That can be done by obtaining the total number by :- R-L+1

And dividing the total count of prime numbers by the total numbers:
Probability of finding the
a prime number is ⇒ ( float ) count of prime numbers/ sum

Why this solution gets WA?? Any ideas?


Seeing a few accepted submissions it seems that you had to print the answer upto exactly 6 decimal places.


Yes, That is precisely the error. Maybe the tester program is not comparing doubles, but strings.

Anyways, Thanks.