PRPR3 - Editorial

editorial
, , ,
1

#PROBLEM LINK:

Practice

Contest

Author: Suthirth V

Tester: Suthirth V

Editorialist: Suthirth V

#DIFFICULTY:

Simple

#PREREQUISITES:

Radical - The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 x 32 x 7, so rad(504) = 2 x 3 x 7 = 42.

Sieve of Eratosthenes - Python Implementation

#PROBLEM:

Elon Musk has trained N ensembles of neural networks, each given an index from 1 to N, to power a self-replicating robot. Owing to the complexities in interstellar travel, he has space for only one ensemble. Empirically, he finds that the combined intelligence I of the nth ensemble is given by the following equation:

I(n) = Product of the prime factors of n

For example, the intelligence of the 18th ensemble is given by:

I(18) = 2*3 = 6

Given N, help Elon find the index of the ensemble with the maximum intelligence.

(Hint: Brute force will not work for large N. Efficiency of the algorithm is crucial for the survival of the self-replicating bots in deep space.)

#QUICK EXPLANATION:

Compute the radicals by sieving all the numbers and sort them to get the index of the highest radical.

#EXPLANATION:

Let’s define the sieving function which computes the radicals for N numbers.


def compute(N):
    ## initialize the list of radicals
    rads = [1]*(N+1)
    ## loop through the entire list starting from 2
    for i in xrange(2,len(rads)):
        if rads[i] == 1:
            ## instead of switching True/False for prime/not-prime in the original sieve,
            ## multiply the prime factors iteratively to get the radical in the end.
            for j in xrange(i,len(rads),i):
                rads[j] = rads[j] * i
    # once the radicals are generated, sort the list to get the highest radical
    data = [(rads[i],i) for i in xrange(len(rads))]
    data.sort()
    return data[N][1]

Here is a sample of the iterative updates happening to compute the radicals for N=30 for every iteration of i



compute(30)

[1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
[1, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6]
[1, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1, 6]
[1, 1, 2, 3, 2, 5, 6, 1, 2, 3, 10, 1, 6, 1, 2, 15, 2, 1, 6, 1, 10, 3, 2, 1, 6, 5, 2, 3, 2, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 1, 2, 3, 10, 1, 6, 1, 2, 15, 2, 1, 6, 1, 10, 3, 2, 1, 6, 5, 2, 3, 2, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 1, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 2, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 1, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 2, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 1, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 2, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 1, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 2, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 1, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 2, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 1, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 1, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 1, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 1, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 29, 30]
[1, 1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 29, 30]

#ALTERNATIVE SOLUTION:

The other approach would be to brute force it

#AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here