I recently gave a coding round of Adobe on unstop which had the following problem I can't solve: Given an array $$$x$$$ of $$$N$$$ elements and an empty array $$$y$$$. You can remove any element from $$$x$$$ and transfer it to $$$y$$$. You can also choose any element $$$a$$$ from $$$x$$$ and $$$b$$$ from $$$y$$$ and add $$$GCD(a, b)$$$ to $$$score$$$ and then you have to remove $$$a$$$ from $$$x$$$ and transfer it to $$$y$$$ while $$$b$$$ stays in $$$y$$$. You can perform both operations until $$$x$$$ is not empty. Report the maximum $$$score$$$ if you play optimally.
$$$1 \lt = N \lt = 1e4$$$
$$$1 \lt = x[i] \lt = 1e4$$$
Example
Input
N = 5
x = 2 3 4 1 6
Output
8
First delete 6 from x. Now x = [2 3 4 1], y = [6]. Select 3 and 6 then score becomes gcd(3,6) = 3 and x = [2 4 1], y = [6 3]. Choose 4 and 6, score is 3+gcd(4,6)=5, x = [2 1] y = [6 3 4]. Choose 2 and 4, score is 5+2=7. Choose 1 and 2, score is 7+1=8.
Input
N = 4
x = 1 2 3 4
Output
4
Any help is appreciated.
It can be solved using a Maximum Spanning Tree Approach (it works for the given test cases , atleast)
In this problem, each operation after placing the first element contributes a score equal to the gcd of the newly inserted element and some previously inserted element. With an optimal ordering, this is equivalent to choosing a spanning tree on a complete graph (with nodes representing the array elements and edge weights equal to the gcd of their values) so that the sum of the edge weights is maximized.
Hmm, that makes sense.
What I tried was that for a particular value of gcd, calculate how many maximum times can I take it using seive in reverse but it didn't work.
Thanks for the help.
Also, I guess the time complexity of spanning tree approach might be $$$O(N^{2})$$$ as we are traversing on a complete graph?
Yep
i can think this ~~~~~ //this is code
include <bits/stdc++.h>
using namespace std;
int main(){ int n; cin>>n; vectorv(n); for(int i=0;i<n;i++){ cin>>v[i]; } sort(v.rbegin(),v.rend()); map<int,int>mp; for(int j=1;j*j<=v[0];j++){ if(v[0]%j==0){ int div1=j; int div2=v[0]/j; mp[div1]=1; mp[div2]=1; } } int ans=0; for(int i=1;i<n;i++){ int val=v[i]; int maxi=1; for(int j=1;j*j<=val;j++){ if(val%j==0){ int div1=j; int div2=val/j; if(mp.find(div1)!=mp.end()){ maxi=max(maxi,div1); } if(mp.find(div2)!=mp.end()){ maxi=max(maxi,div2); } } } ans=ans+maxi; for(int j=1;j*j<=val;j++){ if(val%j==0){ int div1=j; int div2=val/j; mp[div1]=1; mp[div2]=1; } } } cout<<ans<<endl; } ~~~~~
can u please tell your approach
Yeah we should sort array in descending order as for any v[i] gcd(v[i],b) will be max for b>=v[i] so just keep track of divisors seen so for and iterate over the divisor of v[i] as gcd(v[i],b) will be some divisor of v[i] and check if that divisor is already present in array y then we can get score equal to that divisor for this v[i]
is this seems correct to you?
Test case where it will not work is quite simple. We just need to find X < Y1 < Y2 Such that gcd(x, Y2) > gcd(Y1, Y2) and gcd(X, Y1) > gcd(Y1, 2)
We can do it X = 3*5 = 15 Y1 = 3*11 = 33 Y2 = 5 * 7 = 35 X = [15, 33, 35] Using your algorithm we get gcd(33, 35) + gcd(15, 35) = 1 + 5 = 6 but answer is gcd(15, 33) + gcd(15, 35) = 3 + 5 = 8
hmm understood mistake.. thanks for the idea check my recent blog i have one more interesting problem for you on trees check that out
Let make a graph.
Vertex = X[i] Vertex X[i] and X[j] have a edge if gcd(X[i], X[j]) > 1 How many edges we can have?
So, each X have O(sqrt(X)) divisors. it mean that X can be connected with no more than O(sqrt(X)) vertex -> no more than O(Nsqrt(X)) edges.
let find max spanning tree for each connectivity components and our ans is (number of connectivity components — 1) + (Sum of spanning tree weights)
can you see my approach above will it work?
Great soln. I think we can approximate no.of divisors to an upper bound of around x^(1/3).
I think the true value of edges is around NlogN ~ logN for each vertex
hey! i have posted a recent blog which has very interesting problem on tree please watch out that problem and try to give any solution
how can you say that for any vertex we will not have more than O(Nsqrt(X)) edges?
are we given the elements of X are unique ?? it can be repeating also .
correct me if i am wrong..
if we have X[i] == X[j] it means that we can delete X[j], add to ans X[j] and use only X[i]. After that we have all unique values.
Number of edges would be n*(n-1)/2 , because in worst case every vertex can have gcd > 1 for every other vertex, or we can say every vertex in connected with every other vertex. Am i missing anything?
As I say in previous comment we can use only unique numbers X. After that from every vertex have no more than O(sqrt(X)) edges
okay now you have all even numbers & distinct, now every pair has gcd > 1 ?
gcd(a,b) > 1 means they have a common divisor(!= 1) but for fixed gcd and fixed 'a' there can be multiple b's , isn't it?
So, yes, you are right.
In my head I have something different. I say before, that X_i and X_j have edge if gcd(X_i, X_j) > 1 but in head have that X_j is divisor of X_i. It's was a mistake.
We add edge with X_i and all d that are divisors of X_i and if there no X_j such that X_j == d -> ans -= d
how much time was given for this problem to solve in the coding round?
45 minutes
I think you can do this greedily. What you do first is iterate through d = 1e4 to 1 (I am trying to find out the largest possible gcd with the help of d), then:
1. Initially when all elements are in left(called x in the question) and right(called y in the question) is empty, you can just try to find out if d divides any two (or more) elements in left. If yes, put them the largest in the right.
2. When there are elements on the right, find out if d divides atleast one element in the left and atleast one element in right. If yes, bring these elements in the left to right.
3. Keep repeating till you get d= 1.
As to why this is optimal, suppose instead of putting an element to the right with d'', you put it to the right later at d' (d'' > d'). Then, d'' was viable because there was an element which was also divisible by d'' in the right, and upon discovering d', this won't go away (because you are only adding elements to the right). Therefore, d'' will always be an option, even when dividing by d' and it would make sense to choose d' when d'' is an option.
If there is any error in my approach or some confusion, please tell me (along with my mistake in my proof I am not really good at proofs)!
I think it can work. Don't want to think a lot
If you get time and find shortcomings in the proof, please tell me.
for numbers <= 1e4 there can be atmost (25-50) divisors (lets take it 100)
now sort array in reverse order
now iterate from largest element to smallest
for current element iterate over its divisors (from largest to smallest) and check if any of its multiple has been added to y (easily maintainable using a hashmap)
add it to ans move the current element to array y and increase count for its divisors.
O(100*n*logn) over all test cases
isn't this greedy correct?
Bad testcase:
35 33 15
Your algorithm by iterations:
X = 35, 33, 15 Y = []
take 35
Y = [35, 7, 5, 1]
take 33
33 = 11 * 3, no one of it is in Y -> +1
Y = [35, 33, 11, 7, 5, 3, 1]
take 15
15 = 3* 5, 5 is in Y -> take 5.
ans = 6
best ans is 8
35 & 15 ( + 5)
15 & 33 ( + 3)