You are not logged in. Please login at www.codechef.com to post your questions!

×

PPERM - Editorial

15
3

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

This question is marked "community wiki".

asked 24 Sep '12, 00:56

fushar's gravatar image

3★fushar ♦♦
16345853
accept rate: 0%

edited 02 Oct '12, 20:07

admin's gravatar image

0★admin ♦♦
17.4k347486515

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) tijoforyou3★

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

(24 Sep '12, 01:30) anton_lunyov ♦6★

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) gareve4★

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

link

answered 24 Sep '12, 21:12

foofoo's gravatar image

2★foofoo
764
accept rate: 0%

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.

link

answered 24 Sep '12, 01:24

bcurcio's gravatar image

5★bcurcio
3991416
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) arvindpurohit3★
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) gamabunta1★

@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) arvindpurohit3★
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) anton_lunyov ♦6★

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.

link

answered 24 Sep '12, 17:18

ksh78's gravatar image

5★ksh78
11
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) betlista ♦♦3★

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

link

answered 30 Sep '12, 12:36

yesjee's gravatar image

2★yesjee
11
accept rate: 0%

edited 30 Sep '12, 12:46

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

link

answered 28 Jul '14, 17:12

rach8's gravatar image

2★rach8
13
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×12,235
×2,686
×213
×8
×5

question asked: 24 Sep '12, 00:56

question was seen: 6,513 times

last updated: 24 May '16, 11:24