LEVY - Editorial

anton_lunyov · April 15, 2013, 3:00pm

PROBLEM LINK:

Practice
Contest

Author: Kaushik Iska
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Sieve of Eratosthenes

PROBLEM:

For the given positive integer n ≤ N := 10000 you need to find the number of pairs (p, q) such that p + 2 * q = n and p, q are both primes. You should be able to answer up to 100000 test cases in a second.

QUICK EXPLANATION:

The following solution works fine even when N = 400000. At first let’s find all prime numbers up to N using sieve of Eratosthenes. Then we fill array cnt[] of size N such that cnt[n] denotes the number of required pairs of primes for n. Initially it is filled by zeros. Then we iterate over pairs of primes (p, q) in a simple double loop over array of found primes and increase cnt[p + 2 * q] by 1 for each such pair. Moreover, if p + 2 * q > N we break from the inner cycle over q. Clearly after this double loop array cnt[] will be filled correctly. So after such precomputation we can answer each query in O(1) time. The complexity of such approach is O(N * log log N + (N / log N)² + T). Here N * log log N is the complexity of sieve and N / log N is a approximate number of primes up to N.

Some contestants were curious about the case of even n. Let n = 2 * k. Then from p + 2 * q = n we have p = 2 * (k − q). So p is even prime and hence equal to 2. Then q = k − 1. So for even n answer is 1 if n/2 − 1 is prime and 0 otherwise.

EXPLANATION:

Here we discuss implementation details of the above solution.

To find all primes the following pseudo-code could be used:

for p = 1 to N do
   isPrime[p] = true
for p = 2 to N do
   if isPrime[p] then
      add p to the list of primes
      for n = p * p to N with step p do
         isPrime[n] = false

Let primes denotes the list of found primes.

To fill the array cnt[] the following pseudo-code could be used

for n = 1 to N do
   cnt[n] = 0
for p in primes do
   for q in primes do
      if (p + 2 * q > N) then break
      increase cnt[p + 2 * q] by 1

ALTERNATIVE SOLUTION:

The low limit on N allows to use the following dirty trick. Let’s find array cnt[] using any algorithm that possibly could get TLE and print it to some file as a comma separated list of integers. Then copy this list to the program as an initialization of the actual array cnt[]. Now the program is ready to answer each query in O(1) time. Note also that source limit for this problem is 50000 bytes. So your program should not exceed 50000 characters. But since N is only 10000, hack with initialization of cnt[] would cost only about 26Kb of code which is far from the limit.

The most easiest and straightforward way to perform this hack is the following:

for n = 1 to N do
   cnt = 0
   for q = 1 to n/2 do
      p = n - 2 * q
      if (isPrime(p) and isPrime(q)) then
         cnt = cnt + 1
   print cnt, ","

where isPrime(n) returns whether n is prime and could implemented as follows:

isPrime(n)
   if n < 2 return false
   for d = 2 to sqrt(n) do
      if (n mod d = 0) return false
   return true

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be provided soon.
Tester’s solution can be found here.