USF Editorial

general
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Rahim Mammadi
Primary Tester: Amir Reza PoorAkhavan
Editorialist: Hussain Kara Fallah

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Sieve of Eratosthenes

PROBLEM:

Given an array of N integers (all integers are up to 10^5). Let’s suppose we have taken a non-empty subset of this array. The magical value of this subset is (Number of distinct prime numbers that divides every number of the subset * the size of this subset). Find the subset with the maximum magical number and output this number.

EXPLANATION:

First of all, Number of distinct prime numbers that divide every number of the subset is equivalent to the number of prime factors of GCD of this subset.

Let’s try all possible GCDs. How’s that possible?

If you don’t know Sieve then stop reading and take a look at this link. After that, try to figure out the solution yourself.

What’s the optimal subset for a certain GCD (let’s say K) ?. Clearly, we can take a subset of all of its multiples in the array. Please note that the GCD of this subset would be K or one of its multiples, but that doesn’t affect the answer (Why?). Because we will have the same subset when handling this (multiple of K) which is the real GCD and since it’s a multiple of K, it has at least the same number of prime factors hence, the answer will be updated for sure. So we can safely assume the the GCD is equal to K with no problems.

How to loop over the multiples of a number K?

for(int i = K ; i < MX ; i += K){
    tot += cnt[i]; //you can do anything
}

So our code looks like this:

for(int G = 2 ; G < MX ; G++){ //loop for every possible GCD
    int subsetSize = 0;
    for(int i = G ; i < MX ; i += G) // counting how many multiples there are
        subsetSize += cnt[i];
}

The complexity of this loop is:

\sum_{i = 1}^{MaxValue} \frac{MaxValue}{i}

which is equal to:

MaxValue * \sum_{i = 1}^{MaxValue} \frac{1}{i}

The sum of the series:

\sum_{i = 1}^{MaxValue} \frac{1}{i} \approx log(MaxValue)

So total complexity is MaxValue * log (MaxValue)

There is also a part left for you, which is figuring the number of prime factors. This is easy, and can be done also while doing the Sieve approach (left for you), or you can check the codes.

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution

Editorialist’s solution

1 Like
2

There is no explanation what cnt[i] is. Is it the number of prime factors?

And where are the solution links?

3

for(int i = G ; i < MX ; i += G) // counting how many multiples there are

so it’s clear that i is a multiple of G. and we said 2 lines before that we want to take a subset of all the multiples so it’s the count of multiples in array.

It’s updated anyway

1 Like
4

How are we actually finding the gcd’s of all subsets, I didn’t get that part and also what is the proof for gcd’s prime factors being answer and the prime factors of the subset?

5

We are not finding gcds.

We are fixing gcd, say X and calculating both number of distinct prime factors of X, as well as number of multiples of X present in array using sieve. We take maximum of product of this pair of values, for all valid X.

6

Here are C++ and Python implementations.

7

This is not the sieve of Eratosthenes. In the sieve of Eratosthenes you only loop over multiple of primes. You use the sieve of Eratosthenes to find numbers of prime factors, and do it once before running the test cases.

8

Another approach:

Using the sieve of Eratosthenes precompute two arrays - numbers of prime factors and divisor lists. Create a zero-initialized array of useful numbers corresponding to each gcd value. For each element in the input array for each of its divisors add the contribution of the element to the useful number corresponding to the divisor. This contribution is the number of prime factors of the divisor. The answer is the maximum value in the resulting array.

https://www.codechef.com/viewsolution/21706446

1 Like
9

Code is missing.

1 Like