PROBLEM LINKSDIFFICULTYEASY PREREQUISITESSieve of Eratosthenes, Dynamic Programming PROBLEMYou 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 ith integer is the Xth smallest integer in the first i integers, where X is 1 or a prime number. QUICK EXPLANATIONLet pperm[i] = the number of prime permutations of size i. Let's calculate pperm[i]. The last number (i.e., the ith number) has to be the smallest number or the Xth 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[i1] ways. In other words, pperm[1] = 1 pperm[i] = (1 + primes[i]) × pperm[i1] 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. EXPLANATIONFirst, 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[i1], plus 1 if i is a prime number. primes[0] = 0 for i = 1; i <= maxN; i++: primes[i] = primes[i1] + (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 ith position). From the definition of a prime permutation, the number in the last position has be the smallest number, or the Xth 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[i1]. Therefore, pperm[i] = (1 + primes[i]) × pperm[i1] 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 SOLUTIONCan be found here TESTER'S SOLUTIONCan be found here
This question is marked "community wiki".
asked 24 Sep '12, 00:56

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

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
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 Claim: All the above 6 permutations for N=4 are not valid. Reason: the 4^{th} 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 ith integer is the Xth 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)

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
1
you have to realize that 177M is memory used by JVM, not only yours objects In FAQ is written
maybe that's Look at my submission for TEST problem, I'm not using 178MB of memory
(24 Sep '12, 17:57)

pperm[1] = 1 pperm[i] = (1 + primes[i]) × pperm[i1] i want to know how you got this formulae ???.... anyone plz me ???...... answered 30 Sep '12, 12:36

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

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:
??
I've allowed myself to fix this :) So now the pseudocode is fine.
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