You are not logged in. Please login at www.codechef.com to post your questions!

×

CHGCDG - Editorial

3
1

PROBLEM LINK:

Div1
Div2
Practice

Setter- Kirill Gulin
Tester- Ivan Safonov
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Sieve of Erastothenes, Binary Search

PROBLEM:

Given an array $A$ of $N$ integers, we have to maximize the GCD of all elements of the array. To do that, you can select any array element $A_i$ which is divisible by any number ${d}^{2}$, divide it by ${d}^{2}$ and multiply any other array element by $d$.

QUICK EXPLANATION:

Key to AC- Realize that manipulation of powers of one prime is independent of powers of other primes. Perceiving that this question is more about manipulating prime and their powers rather than some complex mathematics theorem was important.

Make a list of primes, and smallest prime divisors of all numbers in range using sieve. Now, for each prime $p_i$, keep a note of how many array elements are divisible by it, and what is the power of $p_i$ in their prime factorization form. Now whats left is finding what power of this prime can we maximum achieve in final answer using above operations - we can use BSH (Binary Search Heuristics) for this. Repeat for all primes and get an AC :).

EXPLANATION:

This editorial is divided into $2$ sections. The first section will highlight on the pre-processing required, and the second section will feature how to calculate answers using Binary Search Heuristics (BSH).

Note that, I assume you all realize that, using operation of same number (i.e. dividing the same element by ${d}^{2}$ and increasing it by $d$) is useless. It will just reduce the prime power of that prime, which we might want to maximize for GCD.

1. Pre-processing-

It seems kind of obvious that we might need factorization of elements. Also, usually such problems do involve manipulation of prime numbers. Hence the first step is to use sieve of erastothenes to pre-calculate-

  • Prime numbers in range $[1,{10}^{6}]$
  • The smallest prime factor of a given number. This ensures $O(LogN)$ factorization of elements.

The observation to make is that manipulation of exponents of prime factors of $A_i$ are independent. We can choose a prime $d$ every time for our operation so that only the chosen prime gets affected. If this doesnt ring a bell, you can refer to tab below.

View Content

This is important as it helps in realizing that, increasing GCD prime by prime is the way to go. It gives an intuition that - "Ok, initialize GCD=1 for now. Lets pick a prime. Let me see what is the maximum possible power of it I can get for GCD of array using above operations. Multiply answer by it. Lets repeat this until we get answer."

What is the next thing we need if we are to do such manipulations? We'd need the prime numbers and their exponents for all elements of array. I specifically liked the tester's method of storing it (to use it later) and I think it can use some credit :) .Its in tab below for reference.

View Content

2. Binary Search Heuristics-

I hope that the intuition so far, especially that of manipulating prime by prime, is clear to you.

Now, for each prime, we will Binary Search on the highest possible power achievable (of that prime) in the final GCD. It is actually quite simple.

Lets say we have to check if a power $k$ is achievable for some prime $p$. How do we do it? Recall that using our operation, we can reduce the power of $p$ in some $A_i$ by $2$ and increase power in another $A_i$ by $1$. In a way, its like "Sacrifice $2$ powers of some $A_i$ for $1$ power in another element." Since we aim to calculate Gcd, our aim is to maximize the minimum power $p$.

Now, we have to check if we can make exponent of $p$ equal to $k$ in GCD. Hence, it makes sense to calculate how much "excess exponent" of $p$ can we take from "rich $A_i$", and how much exponent do we need to "poor $A_i$" to make exponent of $p$ equal to $k$ in GCD.

It can be elegantly done if you have pre-processed the exponents and primes like tester did. The tester used a vector idx[100001] where $idx[p]$ had "Exponents of $p$ which are $>0$ among all elements of array." Hence, he can simply loop over $idx[p]$ and calculate the excess and deficit exponents. (Do not forget that we are currently checking if we can achieve an exponent of $k$ in GCD).

Now, things are quite simple. If we have gained sufficient exponent from "Rich $A_i$" to give to "Poor $A_i$", then a power of at least $k$ is achievable in the final GCD. We check for the highest power achievable using binary search (proof in tab below).

View Content

The code to implement this is given below :)

View Content

SOLUTION:

The solutions are also pasted in tab below for you guys to see. Please refer to them in case links dont work. @admin may need time to link solutions up :)

Setter

View Content

Tester

View Content

$Time$ $Complexity=$ $O((K+N)logN)$ where $K$ is number of primes in given constraints of $A_i$

CHEF VIJJU'S CORNER :D

1. Is this problem solvable if we raise constraint of $A_i$ to $1 \le A_i \le {10}^{9}$?

2. Usually, many problems using GCD need knowledge of Mobius Function, Euler Totient functions etc. There is a very good blog describing them here

3. Linear Sieve deserves a mention here. :)

4. Prove that you can get an AC by this approach-

View Content

For above approach, solve the following-

  • This approach considers only first $100$ prime number. Validate and comment on its correctness. "Proof by AC" not accepted.
  • Can this approach be extended to $A_i \le {10}^{9}$. Why/Why not?
  • What is the lower bound on number of primes to consider for making it useful for $A_i <{10}^{9}$ and $A_i <{10}^{18}$?

Credits for this question to - @codebreaker123

This question is marked "community wiki".

asked 21 Jul '18, 22:13

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859
accept rate: 18%

edited 23 Jul '18, 16:59

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

(23 Jul '18, 00:44) skyhavoc4★

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

(23 Jul '18, 00:54) vijju123 ♦♦4★

Done. xDDD

(23 Jul '18, 00:55) aryanc4035★
1

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

(23 Jul '18, 00:55) vijju123 ♦♦4★

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

(23 Jul '18, 02:41) rashomon4★

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

(23 Jul '18, 02:45) vijju123 ♦♦4★

Nicely Explained! Keep it up bro :)

(23 Jul '18, 10:38) pant00004★
showing 5 of 7 show all

another possible solution:

  1. let g <- gcd of initial numbers

  2. make a[i] = a[i] / g. new gcd = 1.

  3. Now consider only primes until 100 to find the new solution. We will not be able to add any prime > 100 after the 2nd step. 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. let the answer for A[i]/g -> ans

final solution: ans * g.

This can be extended for A[i] <= 10^9 (by considering primes upto $1000$).

let me know if I am wrong.

link

answered 23 Jul '18, 13:40

codebreaker123's gravatar image

4★codebreaker123
1765
accept rate: 10%

edited 23 Jul '18, 16:58

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859

1

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

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

(23 Jul '18, 14:18) codebreaker1234★

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}$

(23 Jul '18, 14:47) vijju123 ♦♦4★
2

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.

(23 Jul '18, 16:12) codebreaker1234★

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

(23 Jul '18, 16:57) vijju123 ♦♦4★

an excellent observation :)

(23 Jul '18, 20:59) pk3013★

Thank you. :)

(23 Jul '18, 21:05) codebreaker1234★
1

@codebreaker123 Very nice observation. And thanks @vijju123 for the awesome editorial :)

(25 Jul '18, 02:17) iprakhar224★

I found this method also; shake out the initial gcd and then only primes below the cuberoot of the limit can support the 2-for-1 deal.

(15 Aug '18, 05:11) joffan5★
showing 5 of 8 show all

i think the complexity should be k.N.logN, please correct if i am wrong.

link

answered 23 Jul '18, 10:35

vipin_bhardwaj's gravatar image

5★vipin_bhardwaj
2288
accept rate: 10%

edited 23 Jul '18, 10:36

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.

(23 Jul '18, 14:55) vijju123 ♦♦4★
1

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)

(23 Jul '18, 16:15) vipin_bhardwaj5★

Can you please pinpoint the location? Cannot get it.

(23 Jul '18, 21:02) vijju123 ♦♦4★
1

@vipin_bhardwaj exactly, i am also getting similar kind of doubt..

(26 Jul '18, 08:31) hemant_dhanuka5★

@vijju123 Bro, see these lines--> for (int k : id[x]) if (k >= h) now += ((k - h) >> 1); // sum, that we can use for (int k : id[x]) if (k < h) now -= (h - k); // sum, that we need

in idx[x] where x is prime, holds exponent of x in every Ai

so i guess overall complexity will be O(NLogN+k.(summation of number of element id[x] for each prime)*logH)...

if i am right, can u prove that this solution will not give TLE ?

(26 Jul '18, 08:43) hemant_dhanuka5★

please someONe reply?

(27 Jul '18, 20:24) hemant_dhanuka5★
1

I had answered this already in an ans on next page.

I say, lets try to get an upper bound on number of iterations. It cannot be $O(N*K)$ as that'd mean every array element $A_i$ is divisible by each of $k$ primes - not possible based on my previous arguments.

At max, how many iterations can it go then? Each element $A_i$ is divisible by $<log_2N$ primes. So worst case calculated by me was select $logN$ smallest primes such that their product is $<{10}^{6}$. Let it be $X$. Make an array with $N-1$ elements $X$ and one element $1$. That gave $O(NLogN)$ complexity.

(27 Jul '18, 20:40) vijju123 ♦♦4★
showing 5 of 7 show all

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.

link

answered 24 Jul '18, 08:44

codebreaker123's gravatar image

4★codebreaker123
1765
accept rate: 10%

edited 24 Jul '18, 10:16

 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.

link

answered 24 Jul '18, 12:55

arjitkansal's gravatar image

4★arjitkansal
1178
accept rate: 0%

edited 24 Jul '18, 12:57

k.n is of the order n.log(n) as any number can have at-most log(n) factors. So, the actual complexity is n.log(n).log(h).

(24 Jul '18, 14:11) codebreaker1234★
1

Not very straightforward dear. If you assume that the for(int k:id[x]) runs for all $N$ numbers everytime, what is the maximum number of times it can run?

A number can be product of $<20$ distinct prime numbers if $A_i \ {10}^{6}$. So the complexity becomes $O(20*N*LogN) \equiv O(NLogN)$ as shown in editorial.

(24 Jul '18, 17:51) vijju123 ♦♦4★

Difference between (Line 135) ( lli mid=l+(r-l)/2 and lli mid=l+(r-l+1)/2 ) deserves a mention in CHEF VIJJU'S CORNER.
https://www.codechef.com/viewsolution/19315183 (TLE);
https://www.codechef.com/viewsolution/19311716 (AC)

link

answered 23 Jul '18, 00:53

aryanc403's gravatar image

5★aryanc403
2.3k1516
accept rate: 10%

Infinite loop? XD

(23 Jul '18, 00:59) vijju123 ♦♦4★
1

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

(23 Jul '18, 01:01) aryanc4035★

I missed the trick for storing lowest prime divisor for non primes. Good one!

link

answered 23 Jul '18, 01:47

fukra's gravatar image

3★fukra
261
accept rate: 33%

1

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

(23 Jul '18, 02:05) vijju123 ♦♦4★

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

(23 Jul '18, 14:37) codebreaker1234★

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.

(23 Jul '18, 14:54) vijju123 ♦♦4★

Can anyone help me with my solution?

Solution link is:

link text

link

answered 23 Jul '18, 10:45

nikesh48's gravatar image

4★nikesh48
363
accept rate: 20%

The tester solution is showing runtime error in my IDE.

link

answered 23 Jul '18, 14:39

swapnil159's gravatar image

5★swapnil159
2365
accept rate: 19%

1

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

(23 Jul '18, 14:57) vijju123 ♦♦4★
1

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

(23 Jul '18, 15:01) swapnil1595★

Thank you :)

(23 Jul '18, 15:29) vijju123 ♦♦4★

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

link

answered 23 Jul '18, 17:26

asced's gravatar image

3★asced
1
accept rate: 0%

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.

(23 Jul '18, 18:14) vijju123 ♦♦4★

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

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

link

answered 23 Jul '18, 19:42

avinashcodex's gravatar image

3★avinashcodex
1
accept rate: 0%

Your solution is really too detailed,Thank you :)

link

answered 23 Jul '18, 20:18

ceniry's gravatar image

4★ceniry
1
accept rate: 0%

Thank you dear :)

(23 Jul '18, 21:02) vijju123 ♦♦4★

Can you please explain with the help of an example?

link

answered 24 Jul '18, 00:25

sparshkedia's gravatar image

5★sparshkedia
11
accept rate: 0%

If binary search part isnt clear, then you dont fulfil the pre-requisites to solve the question. Please refer to links in pre-requisites.

(24 Jul '18, 17:52) vijju123 ♦♦4★

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

link

answered 26 Jul '18, 00:33

oldbeast's gravatar image

3★oldbeast
11
accept rate: 0%

edited 26 Jul '18, 00:35

1

The vector array power needs to be cleared for every new testcase

(27 Jul '18, 09:58) swapnil1595★

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

link

answered 27 Jul '18, 09:52

cyber_bot's gravatar image

3★cyber_bot
231
accept rate: 0%

Thank you :)

(27 Jul '18, 11:59) vijju123 ♦♦4★

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

link

answered 27 Jul '18, 20:40

hemant_dhanuka's gravatar image

5★hemant_dhanuka
533112
accept rate: 3%

Convert recursive to iterative one.

(28 Jul '18, 13:47) vijju123 ♦♦4★

@vijju123 got Ac, my finding smallest factor for each number using seive was slow regarding max A[i]=10^6..

*O(A[i].log[Ai]) ~~ 2 * 10^8 ==tle so optimised my code little bit, got ac

(29 Jul '18, 21:44) hemant_dhanuka5★

now my code is fastest among all java submission for this problem.. thanks for replying

(29 Jul '18, 21:45) hemant_dhanuka5★

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?

link

answered 14 Aug '18, 23:49

codechefnew's gravatar image

3★codechefnew
1
accept rate: 0%

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

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

link

answered 07 Oct '18, 22:15

amritdevilo's gravatar image

3★amritdevilo
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×864
×815
×314
×301
×96
×23

question asked: 21 Jul '18, 22:13

question was seen: 3,905 times

last updated: 07 Oct '18, 22:15