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
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
Thank you @aryanc403.I will check other editorials as well.
1 Like
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
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
https://www.codechef.com/viewsolution/19318590
using setter solution but only considering primes until 100.
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.
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.