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

×

CHEFPRMS - EDITORIAL

PROBLEM LINK:

Practice
Contest

Setter: Misha Chorniy
Tester: Hasan Jaddouh
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Prime Sieve, or even Square root factorization would suffix, Pre-computation. Number-theory (optional).

PROBLEM:

Answer the queries of form, Given a number $N$, can this number be represented as sum of two semi-primes. Semi-prime is a product of any two distinct prime numbers.

SUPER QUICK EXPLANATION

  • Pre-compute all primes up to $MXN$ (MAX possible value of N) (or $MXN/2$ will also suffice). Calculate all Semi-primes by iterating over all pair of distinct primes.
  • Now, calculate all possible sums which can be represented as sum of two semi-primes, by taking each pair of semi-prime.
  • Answer queries in $O(1)$ time using pre-computed values.

EXPLANATION

For this problem, I am explaining two solutions, Common approach as used by Setter and Tester as well as most teams. The other one is quite an overkill, strange way to solve this problem, used by editorialist only. :D

Setter/Tester Approach

Calculate all the primes in range $[2,MXN]$. This can be done using Sieve of Eratosthenes or we can just naively check each number whether it is a prime or not.

For those unaware of Sieve of Eratosthenes, Enter the secret box.

View Content

Now that we have the list of primes in an array, say $pr$. Now, we need to find the list fo semi-primes. we can iterate over all pairs of Distinct primes take their product and the values in range $[1, MXN]$ are marked as semi-prime. So, now we have the list of semi-primes in range$[1, MXN]$.

Now, Computing final answer is just doing once again, Iterating over all pairs of semi-primes and if their sum is in range $[1, MXN]$, mark the sum as reachable.

Answering queries become simple, as we just need to print whether the sum $N$ is marked reachable or not.

Editorialist's Approach (Not recommended at all :P )

This solution differs from above solution at the computation of list of semi-primes. Give a try to compute list of semi-primes without computing primes. It relies on the formula of Number of factors of a number.

The observation is, that all semi-primes have exactly four factors. (can also be proved eaisly) But, all numbers having four factors are of two types. Both semi-primes and perfect cubes will always have 4 factors. So, we iterate over all numbers, check if it has exactly four factors (including trivial factors) and is not perfect cube. If any number satisfy both criteria, it is marked as semi-prime.

After that, this solution is same as Author/Tester solution.

Time Complexity

Both Solutions have pre-computation time $O(MXN^2)$ for iterating over all pairs of semi-primes, which dominates everything.

For a fact, Sieve of Eratosthenes takes $O(N*log(logN))$ time while Square root factorization takes $O(N*\sqrt{N})$ time.

Queries are answered in $O(1)$ time, taking overall $O(T)$ time.

SO, overall complexity is $O(MXN^2)$.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 14 Oct '18, 14:25

taran_1407's gravatar image

5★taran_1407
3.9k2387
accept rate: 22%

edited 17 Oct '18, 21:29

admin's gravatar image

0★admin ♦♦
19.7k350498541


Why my solution is flagged as wrong answer?I have checked for 200 input and it works on codechef practice compiler.link of my solution. Logic used: Every semi-prime number Has exactly two distinct prime factor and used 'count' variable to count it. Also used 'cnt' variable to take care of repeated prime factor.

link

answered 18 Oct '18, 13:32

ayush_999's gravatar image

2★ayush_999
11
accept rate: 0%

I solved this with a modified seive. We can calculate the semi-primes in the seive function itself and later simply iterate till N/2th number to check for semi-primes. Time complexity: 0(N loglogN + N). Have a look : https://www.codechef.com/viewsolution/20952615

link

answered 18 Oct '18, 14:17

didi17's gravatar image

3★didi17
1
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:

×3,707
×646
×626
×301
×145
×29
×4

question asked: 14 Oct '18, 14:25

question was seen: 1,108 times

last updated: 18 Oct '18, 14:17