2
$\begingroup$

I was given this question by a friend:

"You are given 3 sets of size n, X,Y and Z. Devise an algorithm to find maximum number of different pairings (u,v,w,x) such that u,v,w,x belong to X,Y,Z and X respectively (u is not equal to x) and gcd(u,v,w,x)>1."

My approach is to create new sets S and T, such that S contains pair (u,v) (create a node A) with gcd(u,v)>1 and T contains (w,x) with gcd(w,x)>1 (node B). If gcd(u,v,w,x)>1 add an edge between A and B. Now find maximum matching in this bipartite graph.

But he isn't satisfied and says I didn't use the gcd property and the problem can be reduced significantly. Can this algorithm be improved?

$\endgroup$
  • 3
    $\begingroup$ This problem is from ongoing programming contest. $\endgroup$ – preetsaimutneja Jul 9 '14 at 17:56
  • $\begingroup$ What have you tried, to improve your algorithm? What are your thoughts? Are you familiar with the property that that $gcd(a,b,c) = \gcd(a,\gcd(b,c)) = \gcd(\gcd(a,b),c)$? $\endgroup$ – D.W. Jul 9 '14 at 22:11
  • $\begingroup$ what contest is it from? ref? $\endgroup$ – vzn Jul 10 '14 at 2:29
  • $\begingroup$ codechef.com/JULY14/problems/GNUM $\endgroup$ – preetsaimutneja Jul 10 '14 at 3:40
4
$\begingroup$

Here's one possible hint:

$$\gcd(u,v,w,x) = \gcd(\gcd(u,v),\gcd(w,x)).$$

I expect your problem can also be solved using the techniques in the following paper:


A maximal matching doesn't seem like the right approach. The maximal matching algorithm you list will never choose two 4-tuples $(u,v,w,x),(u',v',w',x')$ such that $(u,v)=(u',v')$. Thus, it won't produce the correct answer to the problem: it won't output the maximum number of different 4-tuples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.