May Cook Off Balanced Arrays Help!

general
, , , ,
1

I tried solving the problem, but kept getting WA. Can someone please tell me the logic to solve it?

1 Like
2

Editorials will come. They have been written. Wait.

1 Like
3

Here’s my approach.

First notice that all the prime factors in the array remain inside the array no matter how many operations you do. So, let’s say we finally want to make array equal to X. So, the product of all the prime factors, exponentiated, should be equal to X^n. This implies if for every prime factor, it’s exponent in the array is multiple of n then such X can be formed.

If the above condition is not satisfied we need to add a new element who should balance the exponents of all the prime factors such that exponent of each prime factor should be divisible by n+1, because the number of elements are increased by 1.

Link to my solution

1 Like
4

Pre-requisites : Prime Factorization

The logic behind the problem is we don’t need to add a number if there exist a number which is equal to the Nth root of the product of all the numbers in the array. This can be easily checked by keeping a map of prime numbers and their sum of powers for all numbers and at last checking whether the sum of powers of every prime factor is divisible by N or not.

However if there is need to insert a new number then we can find the required number by finding the required exponent to be added for each prime number in order to make it divisible by N+1 and at last taking the product of modular exponentiation of every prime number and its required exponent.

You can check my solution below :-
https://www.codechef.com/viewsolution/13702870

2 Likes
5

Hi,i was also getting WA because of a minor bug.
But here is what i did.

  1. First we need to observe that if your N elements in array elements are madeup of prime number p1,p2,p3,…,pZ
    .The array will always balance at p1 x p2 x p3…x pZ .

In second example :

4

25 15 5 27

contains prime number {5,3} . Now you can represent the elements as [5^2,5x3,5^1,3^3].Now to balance it with we have to make it {5x3=15} i.e. output array should be [ 15,15,15,15 ].

So series of steps are(index-1 based):

(1,4,5) [5,5x3,5,(3^3)x5] 2nd element balanced already

(4,1,3) [5x3,5x3,5,(3^2)x5] 1st element balanced

(4,3,3) [5x3,5x3,5x3,3x5] 3rd and 4th element balanced

hence, [15,15,15,15].

2.The above example explains a lot of things i.e. If you prime factorise every element and see what other prime factors they are short of and if you can provide them the required prime numbers from within the array the output will be justdoit. As explained above.This can be done by maintaining a set of all prime numbers in the array i.e. {3,5} and checking every element what it is short of and maintaining a set for every element which consist the prime numbers it is made of.Also record the prime numbers frequency for the array.Now you can check for every element whether you can provide it a particular prime number or not.

3.But if you cannot meet the requirements then you have to introduce an element by going to every element and see what it is short of and recording it.

In First example :

3

4 6 14

this can be represented as [2x2,2x3,2x7] and prime numbers this array is made of {2,3,7} hence the array will balance at {2x3x7}.

So you go to first element and you found it is short of a 3 and 7.

Freq[3]=1,Freq[7]=1,Freq[2]=0.

Then you go to second element and you found it is short of 7.

Freq[3]=1,Freq[7]=2,Freq[2]=0.

And at last you go to third element and you found out it is short of 3.

Freq[3]=2,Freq[7]=2,Freq[2]=0.

So the inserted number will be 3^(2+1) x 7^(2+1) =9261.

+1 is added as the needed element will provide the powers but will still remain as an equal element otherwise it will convert to 1.

Hope this was helpful :slight_smile: &
Please point out the mistakes .

2 Likes
6

Thanks, that explains it perfectly.

1 Like