# CHGCDG - Editorial

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

The time complexity is derived from tester’s solution. He first factorises all array elements in O(NLogN), and then for every prime he applied binary search O(kLogH) where H is the highest power of that prime.

Thats because of their assert statements. Codechef IDE adds extra character at end of file. One way around is, to remove the assert(getchar() == -1); at the end and give 1 extra line after input.

Their assertions are done to make sure there are no trailing spaces in input etc. which might cause NZEC error for some java and/or python users.

OR

replace their assert statements with simple cin/cout or scanf/printf 1 Like

Ohh!!..Okayy, actually there was a mistake in my binary search…I was trying to find that…A great editorial though @vijju123

1 Like

Thank you for A[i]<=10^9 we will need to consider primes till 1000. in general for any n, we need to consider primes till n^1/3.
sorry for not explicitly mentioning that.

2 Likes

inside the while loop of binary search, there is also a for loop which can go upto n, so i think it should be O(k.n.logH)

1 Like

Yesss. Exactly!

Infact, if you consider primes upto {10}^{6}, I feel we can solve it for A_i<{10}^{18} as well. Very decent effort from your side Do you have any prior experience on “Binary Search on Answer”? If no, then please refer to links of pre-requisites or practice a few problems from hackerearthon that specific topic.