Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

This problem idea is borrowed from a recent Croatian programming contest but please don't cheat by looking at the solution outlines :) You are given a set of circles in the plane with their centers on the line y = 0. It is guaranteed that no pair of circles has more than one common point:

enter image description here

On the left side you see the circles drawn in the plane.

Your task is to determine into how many regions the circles divide the plane. A region is an inclusion-maximal contiguous set of points not intersecting any of the circles. For example, in the right half of the picture, the regions induced by the circles are colored distinctly (one color per region).

As you can see, the correct answer in this example is 6. The task is to write a program that computes this answer, given a description of the circles.

Input: The first line of the input contains a number n, the number of circle descriptions to follow (this line is optional, if your solution works without it, it's fine). The following n lines each contain two integers, xi and ri > 0, representing a circle with center (xi, 0) and radius ri. It is guaranteed that no pair of circles has more than one common point. It is further guaranteed that xi and ri don't exceed 109 in absolute value (so they comfortably fit into a 32-bit integer variable).

How you can take your input:

I don't want to restrict that part too much.

You may assume that the input is fed into the program via STDIN or that it is available as the file I in the current directory. You can also assume that is available as a string (including newlines) in a global variable that your program can just access without initializing it.

Output: A single number, the answer to the problem, written to STDOUT or the file O in the current directory.

Rules:

  • Shortest code in bytes wins
  • +200 bytes penalty if your code does not have a runtime + space complexity polynomial in n.
  • -100 bytes reward for worst-case expected runtime + space complexity O(n log n)
  • an additional -50 bytes reward (for a total of -150) for worst-case expected runtime + space complexity O(n)
  • an additional -100 bytes reward (total -250) for deterministic runtime + space complexity O(n)

While assessing the runtime you can

  • assume that hash tables have O(1) expected runtime for insert, delete and lookup, regardless of the sequence of operations and the input data (this might or might not be true, depending on whether the implementation uses randomization)
  • assume that the builtin sort of your programming language takes deterministic O(n log n) time (where n is the size of the input sequence)
  • assume that arithmetic operations on input numbers take only O(1) time
  • not assume that input numbers are bounded by a constant (although they are for practical reasons). In particular, this means that algorithms like radix sort or counting sort are not linear time. In general, really huge constant factors should be avoided.

Example inputs:

2 
1 3
5 1

The correct output here is 3.

3
2 2
1 1
3 1

The correct output here is 5.

4
7 5
-9 11
11 9
0 20

This is the example outlined above (not proportionally correct, but the same topology). The answer is 6.

9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2

The answer is 11.

UPDATE: Please check the newly added section "How to take the input"!

UPDATE 2: 6 days into the challenge, we have the following correct solutions:

  • alephalpha: Mathematica, 122 bytes, O(n) expected time = -28
  • m.buettner (2): Ruby, 133 bytes, O(n log n) = 33
  • MT0: Javascript, 255 bytes, O(n log n) = 155
  • Charles: Javascript, 273 bytes, O(n log n) = 173
  • m.buettner (1): Ruby, 259 bytes, O(n²) = 259

UPDATE 3: Score -28 by alephalpha is the winner!

We can use the following idea for a very compact solution:

Lets intersect the set of circles with the X axis and interpret the intersection points as nodes in a planar graph:

enter image description here

Every circle induces exactly 2 edges in this graph and up to two nodes. We can count the number of nodes by using a hash table to keep track of the total number of distinct left or right borders. We can now use the Euler characteristic formula to compute the number of faces of a drawing of the graph:

V - E + F - C = 1

F = E - V + C + 1

To compute C, the number of connected components, we can for example use depth-first search or a builtin function like alephalpha demonstrated :)

Here is my solution, written in Python (in GoRuby it gets a score of 0):

from collections import defaultdict

adj = defaultdict(list)
n = int(raw_input())
for _ in xrange(n):
    x, r = map(int, raw_input().split())
    adj[x-r].append(x+r)
    adj[x+r].append(x-r)

visited = {}
def dfs(x):
    if x in visited:
        return 0
    visited[x] = 1
    for y in adj[x]:
        dfs(y)
    return 1

edges = 2*n
vertices = len(adj)
components = sum(dfs(x) for x in adj)
print edges - vertices + components + 1
share|improve this question
    
Are some of those bonuses decoys? –  user2357112 Mar 26 at 23:02
    
@user2357112 Don't assume it can't be done unless you can prove it ;) –  Niklas B. Mar 26 at 23:28
    
Well, with inputs guaranteed to fit in a machine integer, we could use a radix sort and call it O(n). I hate assuming restricted input size, because strictly speaking, it means there are finitely many possible inputs. –  user2357112 Mar 26 at 23:46
    
@user2357112 No, I said you cannot assume the integers to be bounded while assessing the asymptotics, so neither radix sort nor counting sort would be linear time and space. That they fit into a word is just to make arithmetics "real" O(1) and for practical reasons (bounded variable width in most languages) –  Niklas B. Mar 26 at 23:47
    
@NiklasB. if I have an algorithm in which the only component with superlinear complexity is the sorting, to I have to implement merge sort if my language uses quick sort, in order to get the n log n bonus? Also, I do have new conceptually new solution. Should I post a new answer of replace the old one? (I'd prefer the former, in case my new solution isn't actually correct) –  Martin Büttner Mar 27 at 12:09

6 Answers 6

up vote 2 down vote accepted

Mathematica, 125 122 - 150 = -28 chars

I don't know the complexity of the built-in function ConnectedComponents.

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&

Usage:

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&[
"9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2"]

11

share|improve this answer
    
I think we can safely assume that ConnectedComponents has linear expected worst-case complexity, so if there are O(n) components, this would be fine. I don't understand Mathematica, so I can't tell whether it is O(n) overall and qualifies for the -150 bonus? I think it does. Do I just run it with input in STDIN? –  Niklas B. Mar 29 at 15:51
    
@NiklasB. his input method is just passing a string variable to an anonymous function. so I think that should qualify. as for the output, in Mathematica this will simply result in the number ending up in console output, so that should probably be fine, too. –  Martin Büttner Mar 29 at 15:57
    
I've verified the correctness of this, so I think with a score of -28 this is the new leader. Congratulations! –  Niklas B. Mar 29 at 16:17
    
@NiklasB. why only 150? Which part of the algorithm has superlinear worst-case complexity? –  Martin Büttner Mar 29 at 17:17
    
@m.buettner 150 is for O(n) expected time. For graphs with arbitrary numbers as nodes, implicitly defined like here, you just can't find the number of CCs in linear time, which can be shown by reducing element distinctness to connected components. I think we can also reduce element distinctness to the original problem –  Niklas B. Mar 29 at 17:32

Ruby - 312 306 285 273 269 259 characters

This answer has been superseded by my other approach which uses considerably less characters and runs in O(n log n).

Okay, let's go. For starters, I just wanted a working implementation, so this is not algorithmically optimised yet. I sort the circles from largest to smallest, and build a tree (circles included in other circles are children of those larger ones). Both operations take O(n^2) at worst and O(n log n) at best. Then I iterate through the tree to count areas. If the children of a circle fill up its entire diameter, there are two new areas, otherwise there is just one. This iteration take O(n). So I have overall complexity O(n^2) and qualify for neither reward nor penalty.

This code expects the input without the number of circles to be stored in a variable s:

t=[]
s.lines.map{|x|x,r=x.split.map &:to_i;{d:2*r,l:x-r,c:[]}}.sort_by!{|c|-c[:d]}.map{|c|i=-1;n=t
while o=n[i+=1]
if 0>d=c[:l]-o[:l]
break
elsif o[:d]>d
n=o[:c]
i=-1
end
end
n[i,0]=c}
a=1
t.map &(b=->n{d=0
n[:c].each{|c|d+=c[:d]}.map &b
a+=d==n[:d]?2:1})
p a

Ungolfed version (expects input in variable string):

list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_i
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius, children:[]}
}
list.sort_by! { |circle| -circle[:d] }
tree = []
list.map { |circle|
  i = -1
  node = tree
  while c=node[i+=1]
    if circle[:x]<c[:l]
      break
    elsif circle[:x]<c[:r]
      node = c[:children]
      i = -1
    end
  end
  node[i,0] = circle
}
areas = 1
tree.map &(count = -> node {
  d = 0
  i = -1
  while c=node[:children][i+=1]
    count.call c
    d += c[:d]
  end
  areas += d == node[:d] ? 2 : 1
})
p areas
share|improve this answer
    
@NiklasB. yes that test case would be nice. The relation that defines the edges in my tree is simply inclusion of one circle in another. Since on circle can't be contained in two circles that don't contain each other (due to the "one intersection" condition), I don't see how this could be a DAG. –  Martin Büttner Mar 27 at 0:00
    
Are a node's grandchildren also its children? –  user2357112 Mar 27 at 0:05
    
@user2357112 no, because they can only split their direct parent –  Martin Büttner Mar 27 at 0:06
    
@NiklasB. If I run it with the example in your question, I get 11. For the one in your comment 9. –  Martin Büttner Mar 27 at 0:21
    
@NiklasB. wait, I actually get 10 and 8 with my ungolfed version, but 11 and 9 with my current golfed version :D –  Martin Büttner Mar 27 at 0:22

Ruby, 203 183 173 133 - 100 = 33 characters

So here is a different approach. This time, I sort the circles by their left-most point. Circles touching at their left-most point are sorted from largest to smallest. This takes O(n log n) (well, Ruby uses quick sort, so actually O(n^2) but implementing merge/heap sort is probably beyond the scope of this challenge). Then I iterate over this list, remembering all left-most and right-most positions of the circles I have visited. This allows me to detect if a series of circles connects all the way across an enclosing larger circle. In this case, there are two subareas, otherwise just one. This iteration takes only O(n) giving a total complexity of O(n log n) which qualifies for the 100 character reward.

This snippet expects the input to be supplied via a file in the command-line arguments without the number of circles:

l,r={},{}
a=1
$<.map{|x|c,q=x.split.map &:to_r;[c-q,-2*q]}.sort.map{|x,y|a+=r[y=x-y]&&l[x]?2:1
l[y]=1 if l[x]&&!r[y]
l[x]=r[y]=1}
p a

Ungolfed version (expects input in a variable string):

list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_r
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius}
}
list.sort_by! { |circle| circle[:l] + 1/circle[:d] }
l,r={},{}
areas = 1
list.map { |circle|
  x,y=circle[:l],circle[:r]
  if l[x] && r[y]
    areas += 2
  else
    areas += 1
    l[y]=1 if l[x]
  end
  r[y]=1
  l[x]=1
}
p areas
share|improve this answer
    
Unfortunately this fails for all the larger testcases. It is fast though ;) I don't have a small failing example this time, but you can find the test data on the contest website I linked to (it's contest #6) –  Niklas B. Mar 27 at 15:34
    
The first failing testcase is kruznice/kruznice.in.2 which is the first "real" test case so I assume there is something fundamentally wrong woth the algorithm or implementation. Does it work correct with arbitrarily nested circles? –  Niklas B. Mar 27 at 15:38
    
@NiklasB. thanks, I'll have a look into the test cases (might take me until tomorrow night to fix it though) –  Martin Büttner Mar 27 at 15:41
    
@NiklasB. I figured out the problem and the minimum failing example requires 5 circles: -1 1 1 1 0 2 4 2 0 6. I'll think about how to fix this by tomorrow night (hopefully). –  Martin Büttner Mar 27 at 18:20
    
Your complexity analysis seems to assume that associative array access is constant time. That seems unlikely to be true in the worst case. –  Peter Taylor Mar 27 at 18:29

Julia - 260 -100(bonus?) = 160

Interpreting the circles as figures with vertices (intersections), edges, and faces (areas of the plane) we can relate each other using Euler characteristic, so we only need to know the number of "vertices" and "edges" to have the number of "faces" or regions of the plane with the formula written below: Euler characteristic

UPDATE: By thinking a while i figured out that the problem with my method was only when circles where not connected, so i came with an idea, why not artificially connect them? So the whole will satisfy the Euler formula.

Circles Example

F = 2+E-V (V=6, E=9)

[Dont work with nested circles, so its not an answer of the problem for general cases]

Code:

s=readlines(open("s"))
n=int(s[1])
c=zeros(n,2)
t=[]
for i=1:n
    a=int(split(s[i+1]))
    c[i,1]=a[1]-a[2]
    c[i,2]=a[1]+a[2]
    if i==1 t=[c[1]]end
    append!(t,[c[i,1]:.5:c[i,2]])
end
e=0
t=sort(t)
for i in 1:(length(t)-1) e+=t[i+1]-t[i]>=1?1:0end #adds one edge for every gap
2+2n+e-length(unique(c)) # 2+E-V = 2+(2n+e)-#vertices
share|improve this answer
    
I think your program will fail for 2 -10 1 10 1. –  Niklas B. Mar 27 at 0:39
    
"It is guaranteed that no pair of circles has more than one common point." so i think it will not apply :) –  CCP Mar 27 at 0:44
    
@CCP They have zero common points. n=2, the circles are (C=(-10,0), r=1) and (C=(10,0), r=1) –  Niklas B. Mar 27 at 0:44
1  
Doesn't the graph have to be connected to apply the Euler characteristic? –  user2357112 Mar 27 at 1:13
1  
Ah, here is a simple case: 4 0 2 1 1 10 2 11 1 But I don't think I can give you a lot more test cases, that would be a bit unfair –  Niklas B. Mar 27 at 2:22

Spidermonkey JS, 308, 287, 273 - 100 = 173

I think if I rewrote this in Ruby or Python I could save characters.

Code:

for(a=[d=readline],e={},u=d(n=1);u--;)[r,q]=d().split(' '),l=r-q,r-=-q,e[l]=e[l]||[0,0],e[r]=e[r]||[0,0],e[r][1]++,e[l][0]++
for(k=Object.keys(e).sort(function(a,b)b-a);i=k.pop();a.length&&a.pop()&a.push(0)){for([l,r]=e[i];r--;)n+=a.pop()
for(n+=l;l--;)a.push(l>0)}print(n)

Algorithm:

n = 1 // this will be the total
e = {x:[numLeftBounds,numRightBounds]} // imagine this as the x axis with a count of zero-crossings
a = [] // this is the stack of circles around the "cursor".  
       // values will be 1 if that circle's never had alone time, else 0
k = sort keys of e on x
for each key in k: // this is the "cursor"
  n += key[numLeftBounds] // each circle that opens has at least one space.
  k[numRightBounds].times {n += a.pop()} // pop the closing circles. if any were never alone, add 1
  k[numLeftBounds].times {a.push(alwaysAlone)} // push the opening circles
  if !a.empty():
     set the innermost circle (top of stack) to false (not never alone)
  fi
loop

I'm not terribly great at big O notation, but I think that's O(n) since I'm effectively looping through each circle 3 times (create, left, right) and also sorting the map's keys (and I sort for O(n log n) but that disappears). Is this deterministic?

share|improve this answer
    
If anyone has any advice on how to combine the r loop and the l loop into one statement, i'd appreciate it. –  Not that Charles Mar 28 at 12:55
    
Cheers :) Looks to me like your runtime is indeed O(n log n), due to the sort, which would be -100. I will let you know whether it passes all test cases. –  Niklas B. Mar 28 at 14:00
    
Nice, your program passes all test cases on the first try. I think something like this (sweepline with some state maintained in a stack) was the official solution from the problem authors. Your program gets a total score of 173 –  Niklas B. Mar 28 at 14:56
    
@NiklasB. Thanks! –  Not that Charles Mar 28 at 18:03
    
I was trying a much more robust solution with overlapping circles.... then I saw that they could only intersect at one point. –  Not that Charles Mar 28 at 18:48

JavaScript (ES6) - 255 254 Characters - 100 250 Bonus = 155 4

R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Assumes that the input string is in the variable S and outputs the number of regions to the console.

R=/(\S+) (\S+)/ym;                  // Regular expression to find centre and width.
N=1;                                // Number of regions
w=l=0;                              // Maximum width and minimum left boundary.
X=[];                               // A 1-indexed array to contain the circles.
                                    // All the above are O(1)
for(;m=R.exec(S);){                 // For each circle
    X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};
                                    // Create an object with w (width), l (left boundary)
                                    // and r (right boundary) attributes.
    l=k<l?k:l;                      // Update the minimum left boundary.
    w=j<w?w:j                       // Update the maximum width.
}                                   // O(1) per iteration = O(N) total.
M=[];                               // An array.
X.map(x=>M[(x.l-l+1)*w-x.w]=x);     // Map the 1-indexed array of circles (X) to a
                                    // sparse array indexed so that the elements are
                                    // sorted by ascending left boundary then descending
                                    // width.
                                    // If there are N circles then only N elements are
                                    // created in the array and it can be treated as if it
                                    // is a hashmap (associative array) with a built in
                                    // ordering and as per the rules set in the question
                                    // is O(1) per insert so is O(N) total cost.
                                    // Since the array is sparse then it is still O(N)
                                    // total memory.
s=[];                               // An empty stack
i=0;                                // The number of circles on the stack.
M.map(x=>{                          // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

The time complexity is now O(N).

Test Case 1

S='2\n1 3\n5 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 3

Test Case 2

S='3\n2 2\n1 1\n3 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 5

Test Case 3

S='4\n7 5\n-9 11\n11 9\n0 20';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 6

Test Case 4

S='9\n38 14\n-60 40\n73 19\n0 100\n98 2\n-15 5\n39 15\n-38 62\n94 2';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 11

Test Case 5

S='87\n-730 4\n-836 2\n-889 1\n-913 15\n-883 5\n-908 8\n-507 77\n-922 2\n-786 2\n-782 2\n-762 22\n-776 2\n-781 3\n-913 3\n-830 2\n-756 4\n-970 30\n-755 5\n-494 506\n-854 4\n15 3\n-914 2\n-840 2\n-833 1\n-505 75\n-888 10\n-856 2\n-503 73\n-745 3\n-903 25\n-897 1\n-896 2\n-848 10\n-878 50\n-864 2\n0 1000\n-934 6\n-792 4\n-271 153\n-917 1\n-891 3\n-833 107\n-847 3\n-758 2\n-754 2\n-892 2\n-738 2\n-876 2\n-52 64\n-882 2\n-270 154\n-763 3\n-868 72\n-846 4\n-427 3\n-771 3\n-767 17\n-852 2\n-765 1\n-772 6\n-831 1\n-582 2\n-910 6\n-772 12\n-764 2\n-907 9\n-909 7\n-578 2\n-872 2\n-848 2\n-528 412\n-731 3\n-879 1\n-862 4\n-909 1\n16 4\n-779 1\n-654 68\n510 490\n-921 3\n-773 5\n-653 69\n-926 2\n-737 3\n-919 1\n-841 1\n-863 3';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Outputs: 105

Previous Version

C=S.split('\n');N=1+C.shift()*1;s=[];C.map(x=>x.split(' ')).map(x=>[w=x[1]*1,x[i=0]*1+w]).sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d).map(x=>{while(i&&s[i-1][1]<x[1])N+=s[--i][0]?0:1;i&&(s[i-1][0]-=x[0]);s[i++]=x});while(i)N+=s[--i][0]?0:1

With comments:

C=S.split('\n');                    // Split the input into an array on the newlines.
                                    // O(N)
N=1+C.shift()*1;                    // Remove the head of the array and store the value as
                                    // if there are N disjoint circles then there will be
                                    // N+1 regions.
                                    // At worst O(N) depending on how .shift() works.
s=[];                               // Initialise an empty stack.
                                    // O(1)
C .map(x=>x.split(' '))             // Split each line into an array of the two values.
                                    // O(1) per line = O(N) total.
  .map(x=>[w=x[1]*1,x[i=0]*1+w])    // Re-map the split values to an array storing the
                                    // radius and the right boundary.
                                    // O(1) per line = O(N) total.

  .sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d)
                                    // Sort the circles on increasing left boundary and
                                    // then descending radius.
                                    // O(1) per comparison = O(N.log(N)) total.
  .map(x=>{                         // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

The total time complexity is O(N) for everything except the sort which is O(N.log(N)) - however replacing this with a bucket sort, this will reduce the total complexity to O(N).

The memory required is O(N).

Guess what is next on my todo list... bucket sort in less than 150 characters. Done

share|improve this answer
    
Bucket sort has only average complexity O(n) (in fact O(n+k)), but O(n^2) or O(n log n) worst case depending on the sorting algorithm used within buckets, so you'd need to do it in 50 characters. –  Martin Büttner Mar 29 at 10:32
    
@m.buettner - Bucket sort can be done in O(N) worst-case complexity. It relies on careful choice of the buckets and an O(1) algorithm to assign to buckets. I've done it before (and proved it) and I just need to transfer the code to JavaScript. The algorithm above is already O(N.log(N)) so the only improvement is to get an O(N) sorting algorithm. –  MT0 Mar 29 at 10:43
    
I'd be interested in that proof and corresponding choice of buckets. :) –  Martin Büttner Mar 29 at 10:44
    
cs.princeton.edu/~dpd/Papers/SCG-09-invited/… (on page 556) gives an example of an O(N) bucket sort. archive.org/stream/PlanarityTestingByPathAddition/… (page 75) gives an example of a O(N) combined DFS search and bucket sort (time complexity is discussed on page 76). –  MT0 Mar 29 at 14:55
1  
@Mt0 hold on there, you might to read my addition to the complexity section of the question. With unbounded numbers sorting in linear time is most definitely impossible –  Niklas B. Mar 29 at 15:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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