You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFSSET - Editorial

12
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.

This question is marked "community wiki".

asked 27 Nov '16, 01:11

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 27 Nov '16, 15:35


@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.

link

answered 27 Nov '16, 10:26

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

edited 27 Nov '16, 18:53

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

(27 Nov '16, 11:04) akki284★

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

link

answered 27 Nov '16, 16:05

ritik_27's gravatar image

5★ritik_27
21
accept rate: 0%

@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$.

link

answered 27 Nov '16, 19:06

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

Weak test cases For the subtask 1 and subtask 2. If someone just printed the 'n' i.e. no of elements in an array and he got 30 points.

Input

2

3

2 2 2

4

7 7 7 7

Output (Correct one)

0

0

but if someone printed

3

4 he got right answer,which is obviously wrong.

check here

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

link

answered 28 Nov '16, 02:05

manishkc's gravatar image

4★manishkc
814
accept rate: 0%

edited 28 Nov '16, 02:08

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 !

link

answered 27 Nov '16, 02:31

bansal1232's gravatar image

5★bansal1232
2.8k1419
accept rate: 16%

Can you describe more specifically what do you exactly mean?

(27 Nov '16, 03:09) pkacprzak ♦♦5★

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?

(27 Nov '16, 10:10) bansal12325★

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

(27 Nov '16, 15:36) pkacprzak ♦♦5★

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

link

answered 27 Nov '16, 03:36

hulk_baba's gravatar image

4★hulk_baba
9310
accept rate: 0%

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

(27 Nov '16, 05:30) pkacprzak ♦♦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!

link

answered 27 Nov '16, 04:44

aditya211935's gravatar image

4★aditya211935
111
accept rate: 0%

@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).

(27 Nov '16, 11:56) srd0915★

"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". :)

link

answered 27 Nov '16, 18:03

code_hard123's gravatar image

6★code_hard123
7818
accept rate: 7%

@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

link

answered 27 Nov '16, 18:46

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

edited 27 Nov '16, 18:48

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

(27 Nov '16, 19:15) code_hard1236★

@code_hard123 I too agree on that statement!

(27 Nov '16, 19:27) nikhil_chandak5★

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.

link

answered 27 Nov '16, 18:51

lokesh999's gravatar image

2★lokesh999
41
accept rate: 0%

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.

link

answered 27 Nov '16, 19:06

tej_17's gravatar image

4★tej_17
313
accept rate: 0%

edited 27 Nov '16, 19:14

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

(27 Nov '16, 19:15) srd0915★

@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.

link

answered 27 Nov '16, 19:13

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

Can Someone Help me with thi problem.I implemented the same idea but got WA. https://www.codechef.com/viewsolution/14289019

link

answered 19 Jun '17, 13:24

saisurya027's gravatar image

4★saisurya027
1667
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×639
×199
×28

question asked: 27 Nov '16, 01:11

question was seen: 2,683 times

last updated: 19 Jun '17, 13:24