1
$\begingroup$

I recently got asked the following question:

A set of $n$ cities are numbered from 1 to $n$. Given a positive integer $g$, two cities are connected if their greatest common divisor is greater than $g$. The number $n$ may be as large as $10^5$.

Alice has a list of $q$ cities that she'd like to visit. Given Alice's list of $q$ origin cities and $q$ destination cities, return a boolean vector with a 1 in the $i$th position indicating that it's possible to reach the $i$th destination city from the $i$th origin city, and 0 if not. The length of the list $q$ may be as large as $10^5$ as well.

I solved this problem with a quadratic time solution. However, the large upper bound for $n$ and $q$ clearly implies there is a better runtime. I haven't yet seen a way to speed up the creation of the graph, however.

My solution builds the graph in quadratic time, using a union find data structure to handle the component merging, and Euclid's algorithm for computing gcd's.

The fundamental question is whether there exists a faster than $O(n^2)$ algorithm to construct and query an undirected graph, when edges are defined by a pairwise rule, and it appears that every pair $(i, j)$ for $1 \leq i,j \leq n$ needs to be looked at.

$\endgroup$
  • 3
    $\begingroup$ Can you edit the question to credit the source of this problem? (See cs.stackexchange.com/help/referencing.) $\endgroup$ – D.W. Jan 2 '18 at 2:09
  • 3
    $\begingroup$ I encourage you to replace the code with a description of ideas and concise pseudocode. Not everyone where reads Python, and we're not a coding site -- algorithms are on-topic, but code isn't really. $\endgroup$ – D.W. Jan 2 '18 at 2:10
  • $\begingroup$ @D.W. The question came up during an interview, I'd prefer not to say where. $\endgroup$ – LiavK Jan 2 '18 at 3:14
  • $\begingroup$ @D.W. Python strikes me as almost psudocode already. Is there a specific thing in the code that is confusing? $\endgroup$ – LiavK Jan 2 '18 at 3:17
  • 2
    $\begingroup$ Our site policy is that we want questions to be understandable without having to know a particular programming language. One has to know a bit of Python to understand this code (e.g., zip, list comprehensions; I make no claim that's an exhaustive list). And there seems to be no point in including code for gcd or SetUnion, whatever that is -- that just takes up space without providing any illumination about the algorithmic ideas you have in mind. $\endgroup$ – D.W. Jan 2 '18 at 6:05
3
$\begingroup$

Given parameters $n$ and $g$, you want to find the connected components of the graph on $[n] := \{1,\ldots,n\}$ whose edges are $\{(i,j) \in [n] : (i,j) > g\}$. Let us write these edges in a different way: $$ \bigcup_{d=g+1}^n \{(i,j) \in [n]: d \mid (i,j) \} = \bigcup_{d=g+1}^n \{(dI,dJ) : 1 \leq I,J \leq n/d \}. $$ For each $d$, we have a clique on $\lfloor n/d \rfloor$ vertices. We can preserve the same connectivity properties by replacing it with a path: $$ \bigcup_{d=g+1}^n \{(dI,d(I+1)) : 1 \leq I < \lfloor n/d \rfloor \}. $$ The number of edges in the new graph is $$ \sum_{d=g+1}^n \lfloor n/d \rfloor \leq n \sum_{d=g+1}^n \frac{1}{d} = O(n\log n). $$ You can find the connected components using BFS/DFS in time $O(n\log n)$, a large improvement over your quadratic time algorithm.

$\endgroup$
  • $\begingroup$ Hi Yuval, thank you for the answer! I'm still trying to understand it -- is there a reference you can point me at for this technique? Does it have a name? $\endgroup$ – LiavK Jan 2 '18 at 21:31
  • $\begingroup$ I'm still working through understanding this, but this seems really cool. : D $\endgroup$ – LiavK Jan 2 '18 at 21:35
  • $\begingroup$ I can't think of any references, or of any name for this optimization. $\endgroup$ – Yuval Filmus Jan 2 '18 at 21:36
  • $\begingroup$ This is really cool. @Yuval Filmus, can you offer any insights into how you go to this solution? $\endgroup$ – LiavK Jan 2 '18 at 21:46
  • $\begingroup$ When you get more experienced, you will be able to come up with such tricks yourself. $\endgroup$ – Yuval Filmus Jan 2 '18 at 21:48
0
$\begingroup$

Hint: to determine whether there is a path from source $s$ to destination $t$, factor both $s$ and $t$. What properties need to hold true about their factorization, for such a path to exist?

$\endgroup$
1
$\begingroup$

Pseudo code for finding the minimum connected edges.

    n=100
    lst = range(1,101)
    g=10
    ans = list(tuple())
    for d in range(g+1,n+1):
       for i in range(1,n/d):
         ans.append((d*i,d*(i+1)))
    print ans
    print "size="+str(len(ans))

Output:

   [(11, 22), (22, 33), (33, 44), (44, 55), (55, 66), (66, 77), (77, 88), (88, 99), (12, 24), (24, 36), (36, 48), (48, 60), (60, 72), (72, 84), (84, 96), (13, 26), (26, 39), (39, 52), (52, 65), (65, 78), (78, 91), (14, 28), (28, 42), (42, 56), (56, 70), (70, 84), (84, 98), (15, 30), (30, 45), (45, 60), (60, 75), (75, 90), (16, 32), (32, 48), (48, 64), (64, 80), (80, 96), (17, 34), (34, 51), (51, 68), (68, 85), (18, 36), (36, 54), (54, 72), (72, 90), (19, 38), (38, 57), (57, 76), (76, 95), (20, 40), (40, 60), (60, 80), (80, 100), (21, 42), (42, 63), (63, 84), (22, 44), (44, 66), (66, 88), (23, 46), (46, 69), (69, 92), (24, 48), (48, 72), (72, 96), (25, 50), (50, 75), (75, 100), (26, 52), (52, 78), (27, 54), (54, 81), (28, 56), (56, 84), (29, 58), (58, 87), (30, 60), (60, 90), (31, 62), (62, 93), (32, 64), (64, 96), (33, 66), (66, 99), (34, 68), (35, 70), (36, 72), (37, 74), (38, 76), (39, 78), (40, 80), (41, 82), (42, 84), (43, 86), (44, 88), (45, 90), (46, 92), (47, 94), (48, 96), (49, 98), (50, 100)]
   size=101

We can see that edges like (11,33), (11, 44) etc are not part of the set even though they are directly connected.

After we get the minimum number of connected edges we can apply disjoints sets to solve the above question.

$\endgroup$
  • $\begingroup$ What does ans = list(tuple()) do? When writing pseudocode, try to keep things obvious to the reader and avoid things like that, and like assuming that things must be converted to string type before print can handle them. $\endgroup$ – David Richerby Feb 20 at 17:23

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.