 # PPERM - Editorial

Practice

Contest

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
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 = 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
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, 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 2 Likes

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

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

1 Like

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