Cities Around Amsterdam

Computer Science Level 3

Consider this large set of 1D points on the number line . Let $S$ be the set of unordered pairs $(p,q)$ such that $|p - q| \leq 1000$ . How many elements does $S$ contain?

The answer is 53.

4 solutions

Thaddeus Abiy
Jun 28, 2016

While admittedly there are faster approaches( $O(n+k))$ , I will describe an $O(n\log(n) + k)$ algorithm(where $n$ is the number of points and $k$ is the number of pairs that satisfy the property). This algorithm suffices for our case and is easy to understand. We begin by sorting the set of points( $O(n\log(n)$ ). We then proceed to iterate through each point $P_i$ . From there we will go through every point $P_j$ where $j > i$ until $P_j - P_i > 1000$ . This generates all the unordered pairs.

with open('points.txt','rb') as text:
    exec('points='+text.read())

points.sort()
S = set([])
n = len(points)
for i in range(n):
     j = i + 1     
     while j < n:
        p , q = points[i] , points[j]
        if q - p > 1000:
             break
        else:
            S.add((p,q))
        j += 1

print len(S)

EDIT: Despite the problem statement, this algorithm finds all the points and then counts them.(instead of directly counting them). I believe this is a more general and applicable version of the classic computational geometery problem.

This algorithm should be $O(n^2)$ right? Because the worst case is all pairs satisfy the property, $k=n^2$ . I have one slightly better approach is to use Binary Search. After you sort the list $O(n\lg n)$ , for each element you binary search when does it reach $>1000$ . This is $O(n\lg n)$ .

Christopher Boo - 4 years, 11 months ago

Yes that is accurate. Despite the problem statement, I should have clarified I was demonstrating a generating algorithm in my solution instead of a counting algorithm. Traditionally, such algorithms are expressed in terms of both $n$ and $k$ (where $k$ is the number of pairs that are generated). It is so because we can easily assert that such algorithms are at least $\Omega(k)$ (this is not true for the counting case). Therefore, ideally we would like to achieve a $O(n + k)$ complexity . For the algorithm in the solution, after sorting, let $k_i$ be the number of pairs generated when visiting the $i$ th element in the list $x_i$ . Then we do $k_i + 1$ computations for $x_i$ (the extra computation for the point that exceeds the radius ). Running time is thus

$T(n,k) = n\lg n + \sum_{i=1}^{n}{k_i + 1 }= n\lg n +n + \sum_{i=1}^{n}{k_i} = n\lg n + n + k = O(k + n\lg n)$

I believe this doesn't change even if we use binary search to find the index, we would still have to report the $k_i$ elements.

For an $O(n+k)$ algorithm that uses bucketing, take a look at this .

Thaddeus Abiy - 4 years, 11 months ago

I wrote a script in python which returned exactly 10000 more than the answer, can anyone tel me why? l=[the list] s=0 for i in range(10000):

...for n in range(i,10000):

......if abs(l[n]-l[i])<=1000:

.........s+=1

...if i%100==0:

......print(str(i//100)+'%')

(the last bit is just a progress monitor as the function is very inefficient) Just to reiterate the program returned 10053 and I have no idea why. Thanks in advance

William Whitehouse - 4 years, 11 months ago

Your second for loop should be : for n in range(i+1,10000). Else you will end up comparing 10000 same pairs of numbers which differences is 0.

Christopher Boo - 4 years, 11 months ago

Ah yes, It's obvious now that you've pointed it out! Thank you

William Whitehouse - 4 years, 11 months ago

Rushikesh Jogdand
Jun 29, 2016

with open('points.txt','rb') as text:
    exec('a='+text.read())
count=0
for i in range(0,len(a)):
    for j in range(i+1,len(a)):
        if abs(a[i]-a[j])<=1000:count+=1
print(count)

Masbahul Islam
Jul 16, 2016

link text

Janardhanan Sivaramakrishnan
Jul 12, 2016

A MATLAB Code

SetS = dlmread('points.txt',',');
S = 0;
for i = 1:l(ength(SetS)-1)
  Nop = length(find(abs(SetS((i+1):end)-SetS(i))<=1000));
  S = S+Nop;
end
S

This code searches for all points $q$ to the right of a point $p$ in the list, such that $|p-q| \leq 1000$ , in one go. Thus, there would be $9999$ vector comparisons done, as compared to $\frac{9999 \times 10000}{2}=49995000$ scalar comparions.

Cities Around Amsterdam

The answer is 53.

4 solutions

0 pending reports