COOK82B - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Hussain Kara Fallah
Primary Tester: Hasan Jaddouh
Secondary Tester: Istvan Nagi
Editorialist: Udit Sanghi

DIFFICULTY:

EASY

PREREQUISITES:

Simple-Math, Prime-Factorization, Fast-Exponentiation

PROBLEM:

Given an array of numbers, make all elements equal by the following operation.

Divide a number by x if it is divisible
Multiply another number by x.

You may insert another number to do so.

QUICK EXPLANATION:

Let’s call p, the product of all numbers. The answer is “justdoit” if it’s n-th root is a natural number. Else, find the smallest number such that the (n+1)th root of p is a natural number.

EXPLANATION:

We have some key observations here -

1. The operation of dividing a number by X, and multiplying other number by X, can be thought of multiple operations in which we are dividing only by primes, and multiplying only by primes.
2. These primes will be nothing but the all the primes in the prime factorization of X (If a prime p divides X k times, the p will be repeated k times).

So, the problem can be thought of solving individually for each prime.

Let us try to understand what happens for a prime p.
Let us create a list of sum of exponents of p in each A[i].
We want all the elements in this array to be equal.
In a single operation, we can decrease some element and increase the other.
It will be possible to make them equal if each of the element is divisible by n.

Otherwise, you will have to add another exponent such that each element S becomes divisible by n+1 (+1 due to the extra element we are adding).

Suppose the element we are adding has exponent L.

Then, (S+L)(n+1) should be 0. Or, L = 0 if S(n+1) == 0 else L = (n + 1) - s % (n + 1)

So, now we know the exponent for each prime factor of the next number.

The next number will be equal to the product of all (its prime factors)^(its exponent).
Remember to take modulo at each step.
a^b % MOD can be calculated quickly using fast-exponentiation.

EDITORIALIST’s, AUTHOR’S AND TESTER’S SOLUTIONS:

EDITORIALIST’s solution: [Here] 333
AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555

2 Likes
2

I didn’t know maps can be traversed!! thank you, editorialist.

3

Please tag all editorials of Cook 82 with a #cook82 tag, so that its easier to source them out. @mathecodician @admin

1 Like
4

Ok! done .

5

I got Time limit exceeded for my Submission.

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

My Logic is :
I have made and Array pf[] where the frequency of each Prime Factors will be stored

Example =
N : 3
Inputs : 4, 6, 14
Product : 336
Prime Factors : 2, 2, 2, 2, 3, 7

pf[0] : 0

pf 1 : 0

pf[2] : 4

pf[3] : 1

pf[4] : 0

pf[5] : 0

pf[6] : 0

pf[7] : 1

I will find whether the Positive Frequencies are Equal to Multiple of N, so that all factors are divided equally and there is no need to add new Element.
Else, I will store the product of Factor in newInt till that factor’s Frequency <= N.

Please point out the mistakes .

Thanks!!

6

You need to calculate prime factors faster. What u can do is that store all primes till sqrt(1e9) and then you just need to go through these primes for factorization.

7

@mathecodian
Please Explain this :
“…What u can do is that store all primes till sqrt(1e9) and then you just need to go through these primes for factorization.”

8

Test cases are weak in this problem ,check the above link.There might be rejudging.

9

Your F will overflow. 1 ≤ N ≤ 5000 and 1 ≤ A[i] < 10^9 and your F is product of A[i].

10

“In a single operation, we can decrease some element and increase the other.
It will be possible to make them equal if each of the element is divisible by n.”

Why is it necessary for each element do be divisible by n?

1 Like
11

This Editorial for Balanced Array is not so helpful. I am not getting anything out of it.Can anyone else explain the approach in an easier manner? That will be a great help.

12

One thing you can observe is that since when we divide a number by K ,we are also multiplying another number by k.As a result,the product of all numbers will not change.In the end,we know all numbers will be same.Let that number be x.Therefore xxx…till n =original product of numbers or x^n=product.Thus for x to be integral,the power of all prime factors must be divisble by n,or n+1 in case we have to add a new number.

We now compute the sum of exponents of a prime factor of existing number and figure out the minimum number we need to add to make it a factor of n or n+1.Repeat for all prime

2 Likes
13

That’s a really good explanation.thanks for your effort:)

14

@deadwing97 @kingofnumbers @dpraveen Can the editorial for COOK82E (Binary Tree) be added? Thanks