CHEFSSET - Editorial

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!

@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

##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

“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:

@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

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.

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.

@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

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

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

1 Like

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

Can you describe more specifically what do you exactly mean?

Actually, I wrote unofficial editorial to BGQRS, check it out here: BGQRS - Unofficial Editorial - editorial - CodeChef Discuss

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?

@nikhil_chandak
thanks for explaining.and
for implementation you can see this link CodeChef: Practical coding for everyone

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

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

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

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

@code_hard123 I too agree on that statement!