×

EASY

# PREREQUISITES

Sieve of Eratosthenes, Dynamic Programming

# PROBLEM

You are given an integer N. Count the number of prime permutations of size N. A permutation of integers between 1 and N is called a prime permutation of size N if for all i between 1 and N, inclusive, the i-th integer is the X-th smallest integer in the first i integers, where X is 1 or a prime number.

# QUICK EXPLANATION

Let pperm[i] = the number of prime permutations of size i. Let's calculate pperm[i]. The last number (i.e., the i-th number) has to be the smallest number or the X-th smallest number for some prime number X. Therefore, we have (1 + primes[i]) choices for the last number, where primes[i] is the number of prime numbers not greater than i. The rest of the first i - 1 numbers can be permuted in any of the pperm[i-1] ways. In other words,

pperm[1] = 1
pperm[i] = (1 + primes[i]) × pperm[i-1]

The answer is pperm[N]. We can precompute the values of pperm[i] for all i between 1 and 5,000,000, inclusive, and then answer each test case in O(1) time.

# EXPLANATION

First, let's generate prime numbers between 1 and 5,000,000, inclusive. Let isPrime[i] = whether or not i is prime number. We can use Sieve of Eratosthenes algorithm. If you forgot, the pseudocode is as follows.

maxN = 5000000
isPrime[1] = false
for i = 2; i <= maxN; i++:
isPrime[i] = true
for i = 2; i × i <= maxN; i++:
if isPrime[i]:
for j = i × i; j <= maxN; j = j + i:
isPrime[j] = false


After that, build primes[] array, where primes[i] is the number of prime numbers not greater than i. We can use a dynamic programming approach: primes[i] is exactly equal to primes[i-1], plus 1 if i is a prime number.

primes[0] = 0
for i = 1; i <= maxN; i++:
primes[i] = primes[i-1] + (isPrime[i] ? 1 : 0)


Now, let's solve the original problem. There is one important observation here. Actually, we do not care whether the numbers in the permutation are distinct integers between 1 and N, inclusive. We only care about the relative rank of each number (see the definition of prime permutation). Therefore, the N integers actually can be any N distinct integers.

We will use dynamic programming approach. Let the subproblem be pperm[i] = the number of prime permutations of i distinct numbers. The base case is pperm[1] = 1, since a single number is always a valid prime permutation.

Let's calculate pperm[i] for i > 1. Consider the last position (i.e., the i-th position). From the definition of a prime permutation, the number in the last position has be the smallest number, or the X-th smallest number for some prime number X. Therefore, there are (1 + primes[i]) choices for the number in the last position. After we fix the last number, we have to place the remaining i - 1 numbers in the first i - 1 positions in such a way that the whole permutation is a prime permutation. To accomplish that, by definition, the numbers in the first i - 1 positions have to form a prime permutation as well.

The remaining i - 1 numbers are obviously i - 1 distinct integers. By the previous dynamic programming definition, the number of ways to permute i - 1 distinct numbers to form a prime permutation is pperm[i-1]. Therefore,

pperm[i] = (1 + primes[i]) × pperm[i-1]

The answer for a particular N is of course pperm[N].

We have to precompute all values of pperm[i] for all i between 1 and 5,000,000, inclusive. The time complexity of the precomputation is dominated by the complexity of Sieve of Eratosthenes, O(N log N log log N), where N = 5,000,000 in this problem. After that, we can answer each test case in O(1) lookup time.

Do not forget to perform all calculations modulo 1,000,000,007.

# SETTER'S SOLUTION

Can be found here

# TESTER'S SOLUTION

Can be found here

This question is marked "community wiki".

16345853
accept rate: 0%

19.0k348495531

In the seventh line of the sieve, it reads
for j = i × i; j <= maxN; j++:
Shouldn't it be
for j = i × i; j <= maxN; j += i:
??

(24 Sep '12, 01:24)

I've allowed myself to fix this :) So now the pseudocode is fine.

(24 Sep '12, 01:30)

Supossing that we handle all the pair numbers. All i will be odd and j+= i will change from even to odd. We can speed up a little if we use j += i+i

(25 Sep '12, 03:50) 4★

 2 totally got stumped by this question although i see that coal scam is fairly easy, but more people did this? Somehow the statement "The ith integer is the Xth smallest integer in the first i integers, where X is either 1 or a prime number." gives me a headache when i think about it :D answered 24 Sep '12, 21:12 2★foofoo 76●4 accept rate: 0%
 1 Instead of having an array primes, you can build array pperm on the fly having a variable counting how many primes are under the number. This was a difference between TLE and AC for me. answered 24 Sep '12, 01:24 5★bcurcio 399●1●4●16 accept rate: 0% Hi ALL , I am not getting the question itself can someone help me please . what are the result for N=4 , I want to know brute force approach for this also. Thanks A lot (24 Sep '12, 12:11) 1 @arvindpurohit For N = 4, the answer is 18. I believe you know there are 24 permutations for N = 4. If the answer is claimed to be 18, then we claim that 6 of these permutations are not valid. 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 4 Claim: All the above 6 permutations for N=4 are not valid. Reason: the 4th number in each of them is 4. 4s rank among the first 4 numbers {1, 2, 3, 4} is "X = 4". This rank X (= 4), is neither a prime nor 1. Hence, it is not valid. (24 Sep '12, 13:16) @gamabunta : Thanks for your reply. I am still struggling to understand the i-th integer is the X-th smallest integer in the first i integers, where X is 1 or a prime number (25 Sep '12, 18:19) 1 Let our permutation be p1,...,pn. Consider the number pi. Let there exist exactly X numbers <=pi among p1,...,pi. Then X should be 1 or a prime number. In other words if we sort numbers p1,...,pi in ascending order, then X is a position of pi in this sorted array. (25 Sep '12, 20:08)
 0 What was the memory limit for this problem (or is there global memory limit for every kind of problems)? Solution that I submitted during contest (http://www.codechef.com/viewsolution/1370382) contains 3 arrays (2 for longs, 1 for boolean) and I got Runtime Error. This approach fits in 177M (memory that is usually shown for java programs). I know this problem can be solved with one int array, but I'm curious about memory limitations. answered 24 Sep '12, 17:18 5★ksh78 1●1 accept rate: 0% 1 you have to realize that 177M is memory used by JVM, not only yours objects In FAQ is written 64 MB is guaranteed maybe that's -Xmx 64M for Java program, but I'm not sure. Look at my submission for TEST problem, I'm not using 178MB of memory (24 Sep '12, 17:57)
 0 pperm[1] = 1 pperm[i] = (1 + primes[i]) × pperm[i-1] i want to know how you got this formulae ???.... anyone plz me ???...... or anytheorem behind this formulae ??? answered 30 Sep '12, 12:36 2★yesjee 1●1 accept rate: 0%
 0 I am doing the same way..still getting tle..can anyone help please ? http://www.codechef.com/viewsolution/4397044 answered 28 Jul '14, 17:12 2★rach8 1●3 accept rate: 0%
 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:

×14,366
×3,155
×245
×8
×5

question asked: 24 Sep '12, 00:56

question was seen: 6,908 times

last updated: 24 May '16, 11:24