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

×

CLSUMG - Editorial

2
1

PROBLEM LINK:

Practice
Contest

Author: Avijit Agarwal
Tester and Editorialist: Soumik Sarkar

DIFFICULTY:

MEDIUM

PREREQUISITES:

Prime sieve, Fast fourier transform

PROBLEM:

Let $f(x)=$ the number of pairs $(a, b)$ such that $0 \le a \le b < x$ and $a$ and $b$ are prime and $x = a + b$. Given a number $N$, find the number of pairs $(a, b)$ such that $0 \le a \le b < x$ and $f(N) = f(a) + f(b)$.

EXPLANATION:

This problem was inspired by Goldbach's conjecture :D

Let us assume can find $f(x)$ in constant time for any given $x$. Then for a query $N$ naively trying all pairs will result in a complexity of $\mathcal{O}(N^2)$. Instead we can build up a frequency map/array of the sequence $f$ by upto index $N-1$. Let's call this frequency map $cnt$. Now we can count how many pairs add up to $f(N)$ by iterating over suitable $i$ and adding $cnt(i) \times cnt(f(N)-i)$ to the total. Note that we are looking for pairs where $a \le b$ so we must make sure not to double count any pair. The complexity is $\mathcal{O}(N)$ for one query.

This approach relies on the availability of all $f(x)$ in constant time. One way to achieve that would be to calculate all primes upto the required range beforehand using a sieve. Let there be $P$ such primes, then we can compute the array $f$ in $\mathcal{O}(P^2)$ time, but that would be too slow.

For an efficient solution, consider the polynomial $P(x) = x^2 + x^3 + x^5 + .... + x^p$ where in each term the exponent of $x$ is a prime and $p$ is the last prime we need to be concerned with.

$$P(x)^2 = ( x^2 + x^3 + x^5 + ....)^2 = x^4 + 2x^5 + x^6 + 2x^7 + 2x^8 + ...$$

Multipying $x^a$ and $x^b$ gives $x^{a+b}$. Thus in the polynomial above the coefficient of $x^k$ is the number of ways to represent $k$ as a sum of 2 primes. Note that here the pairs $(a, b)$ and $(b, a)$ for $a \ne b$ are counted separately, so the values must be adjusted to suit the given definition of $f(x)$.

Squaring a polynomial of degree $n$ naively takes $\mathcal{O}(n^2)$ time. However there exists the awesome method of Fast Fourier Transform which can be used to efficiently compute the product of two polynomials in $\mathcal{O}(n \log n)$.

The complexity is $\mathcal{O}(N \log N + TN)$.

AUTHOR'S AND TESTER'S SOLUTION:

Author's solution can be found here
Tester's solution can be found here.

asked 16 Apr, 00:47

meooow's gravatar image

6★meooow ♦
6.7k717
accept rate: 48%

edited 20 Apr, 13:59

admin's gravatar image

0★admin ♦♦
19.3k348495534


Never knew we can use fft so easily in python! Can you explain a bit or give some link for understanding the functions involved?

link

answered 17 Apr, 01:38

dishant_18's gravatar image

4★dishant_18
61419
accept rate: 12%

1

You can refer to the documentation for numpy.fft and scipy.fftpack. There is one useful function in scipy.signal, which is fftconvolve that I have used.

(18 Apr, 20:29) meooow ♦6★
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:

×15,005
×2,473
×325
×280
×53
×5

question asked: 16 Apr, 00:47

question was seen: 665 times

last updated: 20 Apr, 13:59