CHGCDG - Editorial

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

Nicely Explained! Keep it up bro :slight_smile:

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

using setter solution but only considering primes until 100. :slight_smile:

1 Like

it does not matter. storing any prime would suffice as smallest prime = 2. So in each iteration number n is getting reduced to atmost n/2, therby guaranteeing factorization in log(n).

Good job. :slight_smile:

This can be extended for A[i] <= 10^9.

I doubt that. The reason is that your assumption - let d be a prime > 100 such that d^2 is divisible by A[i], then if we divide this A[i] by d^2 then A[i] will no longer be divisible by d. will not hold.

Currently, A_i \le {10}^{6}, so say if p>100. If we say that A_i is divisible by p even after dividing by {p}^{2}, then A_i \ge {p}^{3} \implies A_i > {100}^{3} (as p>100) \implies A_i >{10}^{6}. Since A_i \le {10}^{6}, this means p<100

This will not hold for {10}^{9}

Yes, the trick is to store a prime divisor. Else you’d have to factorize in \sqrt{N} which can be a problem at times.