CHEFSSET - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Animesh Fatehpuria
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Number theory, primes, fundamental theorem of arithmetic

PROBLEM:

For a given array A[1..N] of N integers, the goal is to use the minimal number of operations of multiplying some of these integers by any prime numbers, in such a way that after all these multiplications are performed, then for each two possible different elements of the array A[i] and A[j], the value of A[i] \cdot A[j] is a square number.

QUICK EXPLANATION:

Use fundamental theorem of arithmetic to observe that a number K is a square if and only if each prime number than occurs in the unique factorization of K occurs there even number of times. Use this fact to determine the minimum number of operations needed to compute the final result.

EXPLANATION:

First, notice that K is a square number if all of its prime divisors divides K even number of times. This is the crucial fact to come up with the solution of the problem.

For now let’s assume that all input numbers are primes, which corresponds to what we have in the first and the second subtask. As we will see, this assumptions helps a lot with approaching the problem. Later, we will get rid of this limitation, and the resulting solution will be the exact method used in other subtasks.

Let’s pick any element of the array. Let’s assume it is A[i] and that A[i] = p, where p is some prime number. The question is what is the minimum number of times p has to be multiplied by some primes in order to be sure that when it is multiplied with any other number (remember, we have primes only) from the array, the result is a square number?

Since p is prime, it has only one prime in its factorization and it is exactly p. Moreover, it occurs there odd number of times, so in order to make A[i] \cdot A[j] a square number, where A[j] \neq p, then at least A[i] or A[j] has to be multiplied at least once by p, to make the factor of p appearing even number of times in the product. This fact applies to all A[j] \neq p, so in order to make all products A[i] \cdot A[j] to be square numbers for all A[j] \neq p, then either A[i] has to be multiplied at least once by p or each such A[j] has to be multiplied by p.

Here comes the next crucial observation. If we consider S to be a set of all elements of array A with the value p, then first of all, each element of S should be multiplied by the same primes, because if one method minimizes the number of multiplications needed for one element with value p then it can be applied to all elements with value p and it will be optimal for all of them. Thus, all elements in S will be multiplied by the same primes, so their final value will be the same. This implies that a product of any two elements of S after the multiplications are done is a square number. Moreover, since we noticed that in order to make the product of A[i] \cdot A[j], where A[i] \in S and A[j] \not\in S a square number, we either have to multiply A[i] once by p or all A[j] once by p, so if we consider all elements of S at once, then either we multiply each of them by p once or multiply each element not in S by p also once in order to make p a factor occurring even number of times in any of products we consider.

Based on the above observation we can came up with the following approach. Let’s consider all unique primes in the input. Moreover, let c_p be the number of times that p occurs in the input. Then in order to make all products in which exactly one of the elements has initial value p a square numbers, we have to use \min(c_p, N - c_p) multiplications by p.

Subtasks 1 and 2

Solutions to the first two subtasks are the exact implementation of the method described above.

Subtasks 3 and 4

Solutions to the last two subtask are follow ups to the method described above. Just to recall, in these subtasks there can be numbers in the input array that are not prime. However, it turns out that the solution for in this case is very similar to the one described above.

Let’s consider a prime number p occurring odd number of times as a factor of exactly c_p elements of the input array. Then in order to fix the all the products of pairs of elements of A, where exactly one of elements of each such pair has p occurring odd number of times as its factor, we have to multiply either all such c_p elements by p or all N - c_p other elements by p, and the minimum value of these two leads to the optimal solution. So the only thing to do is to first compute the list of all primes below 10^6, which can be done using for example the Sieve of Eratosthenes, and then for each of these primes, accumulate the number of input elements that are divisible by such a prime an odd number of times. For implementation details please refer especially to setter’s solution listed below which exactly matches the method used here.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.
Tester’s solution can be found here.

6 Likes
2

There is mistake in first line of explanation as, Every prime number should divides K even number of times i.e,

First, notice that K is a square number if Every of its prime divisors divides K even number of times…

Please correct this one !

3

Can you describe more specifically what do you exactly mean?

4

how much time you guys @admin need to upload editorial for BGQRS. Isn’t one month sufficient?

5

What is input? Is it all the elements of the array A, or just a single element?
Also, if you could please explain how the answer is calculated for the array (2, 4, 6) using the method prescribed in the editorial, then it would be very helpful. Thank you!

6

Actually, I wrote unofficial editorial to BGQRS, check it out here: https://discuss.codechef.com/questions/86038/bgqrs-unofficial-editorial

7

First, notice that K is a square number if any of its prime divisors divides K even number of times…

According to this line, Suppose K=12, therefore 2 and 3 are prime divisors of it and 2 divides 12 even number of times, so according to you 12 must be square number, Right?

8

@aditya211935 I also didn’t understand the editorial fully. However I guess I can explain how the answer is calculated for the array [2, 4, 6]. N = 3

First of all you look for the primes from 2 to 6, which are 2, 3 and 5.
Now let me expand the prime factorisation of each number in the small list.

2 = 2^1

4 = 2^2

6 = 2^1 * 3^1

Now you can see that 2 is a factor occurring odd number of times for 2 numbers ( 2 and 6 ). Hence, Cp = 2

Now to fix all the products to be a perfect square, the minimum number of modifications required is min(N - Cp, Cp) Thus the answer in our case is min(3-2, 2) = 1.

Then we apply the same procedure for 3 and we see that it occurs odd number of times for only 1 number which is 6. Thus Cp = 1 and minimum number of modifications required is min(3-1, 1) = 1

Thus the minimum number of total alterations required to make each product of the list a perfect square, is 1+1 =2

As a side note, the original array is [2, 4, 6] and if you multiply 4 with 2 and 6 with 3,
the resulting array will be [2, 8, 18]. It is left for the user to check that each product is a perfect square.

2 Likes
9

@nikhil_chandak
thanks for explaining.and
for implementation you can see this link https://www.codechef.com/viewsolution/12141784

10

@aditya211935 input is all the elements of array, and for (2,4,6) you can multiply 4 by 2 and 6 by 3, which will result in 2 operations and the array would be (2,8,18).

11

I changed “any” to “all”, big thanks for pointing it out

12

##Weak test cases for subtask1 and 2##
For the subtask1 and subtask2, I just print the ‘n’ i.e. no of elements in an array and got 30 points.
whereas my code should give the wrong answer as it will fail when the array has all the elements same.

for eg:-

Input

1

3

2 2 2

Output

0

My code prints 3 and got accepted.

Here is my code

1 Like
13

“First, notice that K is a square number if all of its prime divisors divides K even number of times”.

let say K = 9, the prime divisor 3 divides it 3 times which is odd, so according to the above statement
K is not a square number?

I think instead of using the word “divide”, you could have used “frequency of all prime factors in prime factorization of K should be even”. :slight_smile:

14

@code_hard123 I think you didn’t understand explanation statement correctly.

If K = 9, then the prime divisor 3 divides it 2 times ( not 3 times ) as 9 = 3^2 .

Further, if you divide 9 by 3, the quotient is 3, and then if you divide the quotient, which is 3, by 3, the new quotient is 1. That’s it!

You can’t divide anymore and thus you divided 9 by 3 only twice

15

for A={2,4,6,16,64}.
My answer for this test case is 2.
But by above method answer is 3.
Please clear me doubt.

16

Can anyone explain the output for this test case
[2 2 2 3 5]
According to the editorial I think the answer has to be 4, but I think the answer has to be 5 as:
2X2=4,
2X2=4,
2X2=4,
3X3=9,
5X5=25,
As all are perfect squares their product will also be perfect squares.

17

@lokesh999 The answer for A = {2, 4, 6, 16, 64} is 3 not 2. I don’t know how did you calculate by I will try to explain how 3 has to be the correct answer.

N = 5

Let me expand the prime factorisation of each number :

2 = 2^1

4 = 2^2

6 = 2^1 * 3^1

16 = 2^4

64 = 2^6

Now for prime number 2, it occurs odd number of times in the prime factorisation of 2 and 6. Hence Cp = 2.
Therefore minimum number of modifications required is min(Cp, N - Cp) = min(2, 5-2) = 2

Now for next prime number 3, it occurs odd number of times in the prime factorisation of only 6. Hence Cp = 1.
Therefore minimum number of modifications required for 3 is min(Cp, N - Cp) = min(1, 5-1) = 1

Thus total number of alterations required to make each product a perfect square is 2+1 = 3.

1 Like
18

@tej_17 A = {2, 2, 2, 3, 5}.

If you multiply 3 with 3 and 2 you get 18, and 5 with 5 and 2 you get 50. Total number of modifications made = 2 + 2 = 4.

The resulting array is {2, 2, 2, 18, 50}.

It is left for the user to check that each product is a perfect square. If you want to know each step on how this answer is calculated, please look at my above comments.

19

@nikhil_chandak I completely understood that thing. I was just suggesting to use more vivid statement, just to eradicate unnecessary confusion.

20

@tej_17 answer is 4, you can multiply 3 by 3 and 2, and similarly 5 by 5 and 2.