CHGCDG - Editorial

I’m having difficulty in understanding the binary search part . Can you explain with some example.

What am I doing wrong?? I had the same logic but its giving me wrong answer.

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

Your solution is really too detailed,Thank you :slight_smile:

Can you please explain with the help of an example?

The proof to my solution:

Let g be the gcd of A[i]s.
Now the gcd of A[i]/g to will be 1. (Pretty straight forward to see. Consider gcd be x. If gcd > 1, it contradicts that gcd of A[i] is g as every A[i] will then be divisible by g*x)

Now consider any number d> 100. In the best case, d can divide (n-1) numbers and maximum power of d on any of the nimber is 2. So, consider that d^2 divides (n-1) numbers. Now we have 2 cases:

  1. Divide a number by d^2 and multiply the last number by d. The will make the last number divisible by d but the number which was divided by d^2 no longer divisible by d. Which brings us to the same position except now we have (n-2) numbers divisible by d^2 and 1 number divisible by only d and last number still not divisible by d.

  2. Divide the number by d^2 and multiply a number which was already divisible by d^2 by d. In this case, tgere are (n-1) numbers divisble by d^2, 1 by d^3 (lets say this a) and 2 numbers non divisble by d. If you try to divide a by d^2 then a will be divisible by d and multiply a number no divisble by d. It will brng us to the same case as above. (You can prove this by induction that this will also not work)

You can also see that the numbers cant be made divisible by d by using the tester can function for md=1. You need 1 more divisor, how ever you can get int((2-1)/2) * (n-1) divisors = 0.

I rest my case.

2 Likes

for (int k : id[x])
if (k >= h)//Find excess power
now += ((k - h) >> 1); // sum, that we can use

 for (int k : id[x])
     if (k < h)//Find deficit power.
     now -= (h - k); // sum, that we need

Consider this part of the code, it has O(n) complexity in itself.
So the overall complexity should be O(k.n.lg(H)) per test case.
Correct me if I’m wrong anywhere.

1 Like

If anyone can tell me why code is giving me a run error it’ll be great :slight_smile:
https://www.codechef.com/viewsolution/19341290

Very nice,detailed and easy to get editorial.Really loved it.

help me… i am getting tle
solution link
code written in java

Can it be done in this manner:

Calculate total number of times a prime number appears in the factorization of every array elements like in example 3,15,15,27,1024 total number of 3’s are six and 2’s are ten.
Now simply multiply all the prime numbers with count greater than or equal to number of elements+1.

Please tell me if I am wrong?

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

Can some one help me understand, why is my solution giving wrong answer.

problem links are pointing to different problem bro. Nice work btw

Thanks for telling that. The time in hand to prepare editorials was lesser than a drop of sand xD

Done. xDDD

Thank you @aryanc403.I will check other editorials as well.

1 Like

Infinite loop? XD

Yes. xDDDD .
P.S. - Realised one more advantage of xD - bypass limit of 10 character. xD

1 Like

Yes, it guarantees factorization in LogN time. Glad you learned something from the editorial :slight_smile:

1 Like

Why does the condition in the binary search use (r - l > 1) instead of (r > l)?

There are many variants of binary search. Nothing special in that condition.

Its that, if r-l=1, then mid will always be equal to l. Might result in infinite loop. So setter kept r= Max Possible Value+1 (i.e, our answer is between [l,r) instead of [l,r]).