PPERM - Editorial

PROBLEM LINKS

Practice

Contest

DIFFICULTY

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

19 Likes

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.

1 Like

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.

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 :smiley:

2 Likes

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 ???

1 Like

I am doing the same way…still getting tle…can anyone help please ?
http://www.codechef.com/viewsolution/4397044

In the seventh line of the sieve, it reads

for j = i Ă— i; j <= maxN; <b>j++</b>:

Shouldn’t it be

for j = i Ă— i; j <= maxN; <b>j += i</b>:

??

I’ve allowed myself to fix this :slight_smile:
So now the pseudocode is fine.

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

@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.

2 Likes

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

1 Like

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

@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

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.

1 Like