Question: http://codility.com/demo/take-sample-test/number_of_disc_intersections

Question Name: beta2010 or NumberOfDiscIntersections

Interesting question. Does geometry matter here? Not much.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | def solution(A): discs_count = len(A) # The total number of discs range_upper = [0]*discs_count # The upper limit position of discs range_lower = [0]*discs_count # The lower limit position of discs # Fill the limit_upper and limit_lower for index in xrange(0, discs_count): range_upper[index] = index + A[index] range_lower[index] = index - A[index] range_upper.sort() range_lower.sort() range_lower_index = 0 intersect_count = 0 for range_upper_index in xrange(0, discs_count): # Compute for each disc while range_lower_index < discs_count and range_upper[range_upper_index] >= range_lower[range_lower_index]: # Find all the discs that: # disc_center - disc_radius <= current_center + current_radius range_lower_index += 1 # We must exclude some discs such that: # disc_center - disc_radius <= current_center + current_radius # AND # disc_center + disc_radius <(=) current_center + current_radius # These discs are not intersected with current disc, and below the # current one completely. # After removing, the left discs are intersected with current disc, # and above the current one. # Attention: the current disc is intersecting itself in this result # set. But it should not be. So we need to minus one to fix it. intersect_count += range_lower_index - range_upper_index -1 if intersect_count > 10000000: return -1 return intersect_count |

UPDATE on 2015/10/16: here is some pseudo-code to help you understand. Firstly, we convert the 2D problem into 1D. Because all the circles’ center is on x-axis, we can flat them into a 1D segment as [center-radius, center+radius]. Then the number of (unordered) pairs of intersecting discs is the number of intersecting segments. Finally the pseudo-code is:

1 2 3 4 5 6 7 8 9 | def solution(segments): sort the segments according to their begin points heap = [] # maintained with segments' end points result = 0 for segment in segments: remove all segments s in heap, if s.end <= segment.begin result += len(heap) add segment into heap return result |

I was having a really hard time trying to figure out the algorithm. After stumbling upon your solution I was asking myself how is this even possible, how the hell does work? So I took a piece of paper and a pen… And it turned out that the solution is simple.

But while the solution is simple, getting to the solution is the other part… Anyways, thanks, your solution is nice and clean. And works in quite short time [;

My great pleasure to see my code be helpful! Enjoy coding!

Hi, i look to your solution, maybe I miss it at some point, but this comment:

# We must exclude some discs such that:

# disc_center – disc_radius <= current_center + current_radius

# AND

# disc_center + disc_radius <(=) current_center + current_radius

I don't see such implementation on your source code. Can you explain more about it?

The whole block of comments is corresponding to the one line code “range_lower_index – range_upper_index -1”. Drawing it on a paper should be helpful to understand it.

I spent over 5 hours on this, but couldn’t solve it. Sheng, your solution is great. Thank you.

My pleasure to see my code be helpful to others. Enjoy coding!

Does it pass performance tests? It’s O(n*n) and not O(n * log(n)). The improvement is really simple to use binary search to find range_lower_index in the outer loop.

It did pass all tests, and have time complexity O(n*log(n)). Both range_upper_index and range_lower_index are increasing from 0 to discs_count with step 1. So the for-while loop totally counts for O(n).

I agree with you – this is a O(n*n) not O(NlogN )

Could you please explain more? The for-while loop totally counts for O(n). Where does the O(N^2) come from?

Both “for loop” and “while loop” have individual complexities of O(n). As the while loop is inside the for loop then it is O(n*n). Please correct me if I misunderstood the code.

Both “for loop” and “while loop” have individual complexities of O(n). And the while loop is inside the for loop. (You are right)

But it is not to multiply the two for the O(N*N). It is addition to get O(N+N).

range_upper_index is travel from 0 to discs_count-1. So does range_lower_index. SO we do NOT need to care about how many while/for are there. Just pay attention that, in some method, we travel the two variables range_upper_index and range_lower_index in O(N). That is the complexity.

This is definitely a slow O(n*n) solution. As somebody suggested instead of looping in the inner loop over all values, use binary search to find the correct value in the already sorted array

This is definitely not a O(N^2) solution. It is O(N). Don’t be cheated by the two loops. Please pay attention to how the range_upper_index and range_lower_index change and how they control the loops.

This looks to be O(n^2). The outer loop can run for a maximum of n iterations as can the inner while loop. Therefore, since the loops are nested, this is O(n^2). The two loops would only be O(n+1), which incidentally is just O(n), if they came one after the other and were not nested.

And I agree that the correct solution is to use a binary search, which has complexity O(log n). Place this inside of the outer loop and you have the desired O(n log n) performance.

It looks like O(N^2). But it eventually not. Not every for() {while() {}} loop is O(N^2).

I proved the complexity. But you simply insist every two-level-nested loop is O(N^2), which is definitely and definitely wrong.

Just from curosity, can you share your solution with binary search?

Thanks, I see now. While statement loops only once with “range_upper_index=0”. In that case, I think it is better to take it out of the for loop because it is hard to read and causes misunderstanding.

Personally, I do not think you get my solution. While loop cannot be moved outside.

I am sorry. It is hard to descript the solution without a graph. I would like to suggest you to have a piece of paper and a pen, draw the solution, and you will get the complexity.

There exists a O(N) solution to this problem.

https://zhengxucoding.wordpress.com/2015/04/11/codility-numberofdiscintersections/

The solution in the post is also O(N).

You are using a.sort() which is O(N LogN).

Your solution requires sorting, thus it’s O(N logN)

Sorry, forgot the sorting. It is O(NlogN).

Hi Sheng, excellent blog. This is my first comment here. I have a question for you? Why this problem can’t be solved or thinked in this way:

I think if I go over from the first disc (first disc center) to the last one, I can just add the number of disc centers (center) included between the center and the radius of this disc (as long as this value don’t exceed the last disc center).

If the radius of this disc don’t exceed the last disc center, then this disc intersects with “radius” discs. If the radius of this disc exceed the last center, then this disc intersects with all the discs until the last one.

I don’t know why this thinking is wrong. Can you help me?

Sorry, with a simple test I refute this solution. You can disregard this comment 😉

Totally fine. It is great that you got the right direction finally. Enjoy coding!

intersect_count += range_lower_index – range_upper_index -1

I really don’t understand how range_upper_index is removing all the discs that are not intersecting. Can you please explain.

P.S: I did read the comment above that line.

Hello Annesha, sorry for my late reply. The email system got some trouble, and I did not get any notification email. I updated a pseudo-code to demo the idea.

Hi Sheng,

This is an excellent blog, thanks. Could you explain a little bit more about your pseudocode?. Is the heap a max_heap sorted by the ends of segments?. I don’t quite get how the heap structure helps you.

The heap is a min heap. Actually we can use Red-Black-Tree instead of heap. The main point is: with X segments in the structure, we could find the one with leftmost end point in O(logX).

This is my naive sort + binary search solution in C++. I didn’t get 100 for the first try because I ignored the integer overflow. It’s never good idea to have algorithm practice on Friday afternoon, isn’t it?

I have to say that I admire your ability to consider intervals’ start and end coordinates as discrete objects and compare them that way, which I would never be able to do in 40 minutes time limit!

As for the discussion on the time complexity for that while-for loop, I support you! By simply looking at it, it’s O(N^2). However, since both lists have been sorted, we could say the amortized time complexity is O(N). Again, I probably would never try it in any real coding test either…

40 minutes? Sorry, I used couple of days to get the solution~ :——)

You are humble 🙂 I know you are a *******. 🙂

My impression is that all medium level tasks should be completed in 40 minutes. Codility actually recommends 50 to 55 minutes for hard level tasks in real testing environment.

This is quite a challenge for me who’s not a native English speaker. Interpreting the description of the task could take me 20 minutes…It made me think of GRE test…

Anyway, every time I finished a task, I come here to see if there is a better solution. I’d like to let you know your days of work enlighten me a lot! I really appreciate it!

Keep your good work at ******!

Any coder is more than welcome here! And thanks for overrating over me 🙂

Probably the definition of “hard” is not exactly the same for training problem, monthly challenge, and real interview questions, on Codility.

My C# solution that scored 100%:

https://codility.com/demo/results/trainingSCFJRV-2U7/

Ok, I am a bit confused by how the time complexity is calculated. Can you, Sheng, or anyone else comment on this. If I have an Array with N elements and I need to sort it, that adds a time complexity of O(log(N)). If I have a simple loop that walks through all elements of the array, the complexity is O(N). Now, if the sorting and the looping happen separately from each other, shouldn’t the complexity be O(N + log(N)). I thought that a time complexity of O(N * log(N)) means that the sorting happens in each loop.

Based on that, I think that my algorithm posted above has a time complexity of O(2*N + log(2*N)).

Am I wrong?

On one side, the sorting is O(N*logN), not O(logN).

On the other side, O(N + log(N)) = O(2*N + log(2*N)) = O(N). Big O is used the measure the order of complexity, rather than the exact value. FYI, O(N + NlogN) = O(NlogN).

My Java solution that scored 100%:

https://codility.com/demo/results/trainingVATT2P-NGZ/

Wow!! This is O(N) when O(N*log(N)) was expected. I wrote it in python for those interested:

https://codility.com/demo/results/trainingJZE9XG-GXK/

Thanks for your detailed comments! Awesome!

my php-Version that passes 100%

but it gets me a long time to interprete the challenge, confusing for not native speakers

I thought of a similar way of doing it that might be easier to understand. The idea is to just move across the number line from left to right. Whenever you encounter a disc opening, you increment the number of intersections by the number of already open discs, then increment the number of open discs by one. Whenever you encounter a disc closing, you decrement the number of open discs by one.

I don’t fully understand codility lesson… For the example (counting duplicates)

Discs that intersect

0 with (1,2,4)

1 with (0,2,3,4,5)

2 with (0,1,3,4)

3 with (1,2,4)

4 with (0,1,2,3,5)

5 with (1,4)

Pairs of discs that intersect (output 11 without duplicates)

(0,1), (0,2), (0,4)

(1,2), (1,3), (1,4), (1,5)

(2,3), (2,4)

(3,4)

(4,5)

But my code failed for input array[1,1,1], codility says that output should be 3 but I only can see 2 following above logic of deleting duplicates

Discs that intersect

0 with (1)

1 with (0,2)

2 with (1)

Pairs of discs that intersect (output 2 without duplicates) > Codility expects 3!

(1,0), (1,2)

Can you give a clue about what I am understanding wrong? Thanks!

In your given example [1, 1, 1], there are three discs:

#0: center at (0, 0), radius 1;

#1: center at (1, 0), radius 1;

#2: center at (2, 0), radius 1.

The non-duplicate intersects include:

a) #0 and #1;

b) #0 and #2; (you missed this one. Please double read the question description. They are considered as intersect here)

c) #1 and #2.

Hi,

First of all, thank you Sheng for having this helpful blog. I’ve been using it to corroborate each of my answers.

I wanted to share my C++ solution, with O(N) time and O(N) space complexities.

The logic behind my solution started by thinking that I could count intersections from left to right, traversing the array of discs just once. The radius of each disc gives us the number of intersections for each disc, to its left and to its right. To the right, I count intersections for each disc until the end of the disc or the end of the array, whichever comes first. To the left, I count intersections for each disc until the beginning of the disc or the beginning of the array, whichever comes first. But since all right intersections for each disc are considered, some of the left intersections for each disc need to be revised so that they don’t get counted twice.

Much appreciate for the solution with detailed comments! It will be greatly helpful to the others. Thanks and happy new year!

Thank you Sheng for this wonderful blog. It is immensely helpful when comparing own approaches. Contributing to the discussion. Here is a C++ implementation of O(n) solution mentioned on StackOverflow. Scores 100% on OJ.

https://stackoverflow.com/a/4801275/10353406

Here is a naive solution, O(N^2), easy to understand though for the readers.

This can be easily resolved, with a complexity of O(N*N) tough