Problem

We draw N discs on a plane. The discs are numbered from 0 to N - 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders). 

The figure below shows discs drawn for N = 6 and A as follows: 

 There are eleven (unordered) pairs of discs that intersect, namely:

•    discs 1 and 4 intersect, and both intersect with all the other discs; 
•    disc 2 also intersects with discs 0 and 3. 

Write a function:

int solution(vector<int> &A);

that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return -1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, as explained above.

Write an efficient algorithm for the following assumptions:
•    N is an integer within the range [0..100,000]; 
•    each element of array A is an integer within the range [0..2,147,483,647].

Note:

Intersection done manually (by observing above diagram)

Let the discs be identified by their centers as 0^th, 1^st, 2^nd, 3^rd, 4^th and 5^th. The eleven intersection pairs, with some ordering, from left to right, is as follows, without repeating the count of opposite order of same pair. The rule to obtain the pairs is: J+A[J] >= K-A[K].

     0th and 1st 
     0th and 2nd 
     0th and 4th
     1st and 2nd 
     1st and 3rd
     1st and 4th
     1st and 5th
    2nd and 3rd
    2nd and 4th
    3rd and 4th
    4th and 5th

The above eleven pairs can also be obtained, reading the diagram from right to left. In this case, in each pair, the two discs will be ordered in reverse. The rule to use here is K-A[K]  <= J+A[J]. The list of pairs is:

    5th and 4th
    5th and 1st 
    4th and 3rd
    4th and 2nd
    4th and 1st 
    4th and 0th
    3rd and 2nd
    3rd and 1st
    2nd and 1st
    2nd and 0th
    1st and 0th

 “Ordering” has two meanings for this problem. It can mean the order when creating the list of pairs from left to right, based on the diagram. That order is different from the order, in creating the list of pairs from right to left, based on the diagram. Ordering can also refer to the left or right position of each of the discs in each pair.

In the above two lists of pairs, each list has eleven pairs. The eleven pairs are the same, but in either list, each disc is on the opposite side in a particular pair. That is one ordering. The lexical presentation order of both lists, are the opposite of one another. That is the another ordering. So, “unordered” as used in this problem, refers to the non-respect of either or both of these orderings. 

The rest of this document uses the first list of pairs above.

The lesson (tutorial) for this problem is on sorting. So the candidate should expect that sorting is involved somewhere, somehow in the solution.

The above eleven intersection pairs (first list) have been ordered from left to right, using the disc centers of 0, 1, 2, 3, 4, 5 as identifiers. Ordering like this, may be seen as a kind of sorting. In deciding the intersections manually above, the first circle is considered, by its center, focusing on its right end at 1 = 0 + A[0] . Remember that A[J] is the radius whose center is J. The diagram is scanned visually, rightwards. If any left end of a circle on the right, touches the right end of this first circle, or is on the left of it, then that forms an intersection pair with the first circle. The right end of a circle is given by J + A[J], where J is the center of the circle and A[J] is the radius of the circle, centered at J. The left end of a circle ahead, is given by K - A[K], where K is the center of the circle and A[K] is the radius of the circle, centered at K. 

The left ends of circles that touch the right end of the first circle centered at 0, or the left ends of circles that are on the left of the right end of the first circle centered at 0, are circle 1 centered at 1, with left end at -4; circle 2 centered at 2, with left end at 0; and circle 4 centered at 4, with left end at 0 too. The rest of the eight intersection pairs are equally determined (moving rightwards).

O(n²) Solution

The algorithm just described above, is implemented as follows (read through the code):

The output is 11. At app.codility.com/programmers the scoring and detected time complexity for this solution() is:

    Task score : 75% -  Correctness : 87%; Performance : 62%

    Detected time complexity : O(N²) 

Analysis summary

The following issues have been detected: wrong answers, timeout errors.

For example, for the input [1, 2147483647, 0] the solution returned a wrong answer (got 1 expected 2).

Improving the Code

Correcting the  arithmetic overflow error

The reason why the correctness is 87% and not 100%, is because of the following quotations from the report: 

“wrong answers

For example, for the input [1, 2147483647, 0] the solution returned a wrong answer (got 1 expected 2).”

“overflow
arithmetic overflow tests

X WRONG ANSWER: got 1 expected 2” 

One of the assumptions given in the problem is:

·         each element of array A is an integer within the range [0..2,147,483,647]. 

2,147,483,647 is the upper limit on integers. This means the longest radius can be 2,147,483,647. Any number greater than this, has to be declared as a long integer. The first assumption given in the problem is: 

·         N is an integer within the range [0..100,000];

This means the highest index (position of disc) can be about 100,000. 

In the above solution() function, there is the expression,

    J+A[J] 

Imagine that if 100,000 is to be added to 2,147,483,647, then the result would be 2,147,583,647, which is above the integer range. So, the value of A[J] has to be casted to long integer, as follows:

    J+(long)A[J] 

so that the answer will be a long integer, preventing the arithmetic overflow error. To be on the safe side, just cast all the numbers (variables) in,

    J+A[J] >= K-A[K] 

to long, as follows:

    (long)J+(long)A[J] >= (long)K-(long)A[K] 

The code of interest here becomes:

#include <iostream> 
#include <vector>
using namespace std;

int solution(vector<int> &A) {
    int N = A.size();
    int counter = 0;

    for (int J=0;J<N;J++){
        for (int K=J+1; K<N; K++) {
            if ((long)J+(long)A[J] >= (long)K-(long)A[K]) {            
                counter +=1;
            }
            if (counter > 10000000)
                return counter;
        }
    }

    return counter;
}

At app.codility.com/programmers, the scoring and detected time complexity for this solution() becomes:

    Task score : 81% -  Correctness : 100%; Performance : 62%

    Detected time complexity : O(N²) 

Correcting the Slow Speed (Timeout Errors)

For each access of a pair of discs by the above code, the following comparison had to be made: 

            if ((long)J+(long)A[J] >= (long)K-(long)A[K])

If the comparison were true, the counter (which counts the running total of pairs with intersection) had to be incremented as follows:        

                counter +=1;

In cases for which the comparisons were false, the counter was not incremented, and those operations were wasted accesses (operations). Remember that the given vector is: 

    A[0] =1, A[1] = 5, A[2] = 2, A[3] = 1, A[4] = 4, A[5] = 0

Accesses Table

0 and 1 (counted), 0 and 2 (counted), 0 and 3 (wasted),  0 and 4 (counted),  0 and 5 (wasted)

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

                                                            2 and 3 (counted), 2 and 4 (counted), 2 and 5 (wasted)

                                                                                          3 and 4 (counted), 3 and 5 (wasted)

                                                                                                                        4 and 5 (counted)

There are 5 columns in this table. There are 15 operations here. Among the 15 operations, there are 4 wasted operations (accesses). If the wasted operations can somehow be reduced, may be the process will be done within a shorter and acceptable duration. Well, that will still not lead to any significant reduction in the number of operations, for the following reason: 

Note that if there is intersection of all the pairs, then there will be 15 pairs of intersection (and no reduction in the number of operations).

Code for all Discs Intersecting

The table for all discs intersecting and the table for the above problem are presented as follows: 

Accesses for all Discs Intersecting

0 and 1 (counted), 0 and 2 (counted), 0 and 3 (counted), 0 and 4 (counted), 0 and 5 (counted)

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

                                                            2 and 3 (counted), 2 and 4 (counted), 2 and 5 (counted)

                                                                                          3 and 4 (counted), 3 and 5 (counted)

                                                                                                                        4 and 5 (counted)

Accesses for all Discs for Problem Above

0 and 1 (counted), 0 and 2 (counted), 0 and 3 (wasted),  0 and 4 (counted),  0 and 5 (wasted)

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

                                                            2 and 3 (counted), 2 and 4 (counted), 2 and 5 (wasted)

                                                                                          3 and 4 (counted), 3 and 5 (wasted)

                                                                                                                        4 and 5 (counted) 

The difference is that the second table has some wasted accesses (wasted operations). However, app.codility.com/programmers is not really bordered about these wasted operations, for reducing number of operations (number of accesses). For time complexity, app.codility.com/programmers expects the worst case to be 10 operations which is about O(Nxlog₂N), and the best case to be 5 operations which is exactly O(N), the number of discs.

The worst case time complexity occurs when there is no pair of intersection, at all. The best case occurs when all the discs intersect. 

Do not forget that for this problem, there are 5 discs. For the above two tables the variable J begins from 0 and the variable K begins from 1; and making five columns.

For either of the tables above, the first column consists of one operation; the second column consists of 2 operations; the third column consists of  3 operations; the fourth of 4 operations; and fifth of 5 operations. 

Notice that the column numbers for the 15 operations follow the arithmetic progression, where N = 5 and common difference = 1; that is:

    1 + 2 + 3 + 4 + 5 = 15 

Actual Code for All Discs Intersecting

From either of the above tables, if all discs intersect, then there will be 5 operations, as the following code illustrates:

int solution(vector<int> &A) {
    int N = A.size();
    int counter = 0;    // number of intersection pairs    
    int noAddedDiscs = 1; //    assumed to start at 1
    int J=0;      
    
    for(int K=1;K<N;K++) {        
        counter += noAddedDiscs;
        if (counter>10000000) 
            return -1;
        noAddedDiscs++;
    }
    
    return counter;
}

Read through the code, if that is not already done. When K=1, one disc is added to the counter; when K=2, two discs are added to the counter; when K = 3, three discs are added to the counter; when K=4, four discs are added to the counter; and when K=5, five discs are added to the counter; giving a total of 15 intersections, with 5 operations and not 15 operations. Each number is added in one operation. For example, 3 is added in one iteration of the for-loop, and not in 3 iterations of the for-loop. The addition for this case is as follows:

    1 + 2 + 3 + 4 + 5 = 15 :           

five operations (numbers) with a result of 15 .  

Since all discs intersect, before the next iteration of the for-loop, the number of intersections to add (noAddedDiscs) is already determined, at the bottom of the for-loop (except for the first one that is assumed before the for-loop). 

Actual Code for Discs with and/or without Intersections

The above code is for the situation where there is intersection among all the discs (disc 1 intersecting with all the discs; disc 2 intersecting with all the discs, and so on, until disc 5 intersecting with all the discs). Under that perfect condition, the discs are naturally sorted by their left ends and also naturally sorted by their right ends; that is, there are two sorted lists.

So, for the given problem where there are some non-intersecting discs, why not obtain two sorted lists, employ the same code above, and then strike-out the intersection pairs that do not occur (in the problem). The code segment to extract and obtain the two required sorted lists is (read through the code):

    vector<int> left;
    for (int i=0; i<N; i++)
        left.push_back(i-A[i]);
    sort(left.begin(), left.end());
    vector<long int> right;
    for (int i=0; i<N; i++)
        right.push_back((long)i+(long)A[i]);
    sort(right.begin(), right.end());

The condition for intersection pairs has been given above as:

    J+A[J] >= K-A[K] 

The opposite, which is non-intersection is given by:

    K-A[K] < J+A[J] 

and in the code below, it is: left[K]>right[J]. The above for-loop code segment becomes:

    int noAddedDiscs = 1; //    assumed to start at 1
    int J=0;  

    for(int K=1;K<N;K++) {
        while((J<N)&&(left[K]>right[J])) {  //non-intersections 
            J++;
            noAddedDiscs--;  
        }
        
        counter += noAddedDiscs;
        if (counter>10000000) 
            return -1;
            
        noAddedDiscs++;
    }

Read through the code, if that is not already done. In the while-loop, the non-intersection pairs for a value of K, are struck off with noAddedDiscs-- . This corresponds to wasted operations (wasted accesses). J++ is to increment J within the while-loop.

Except for the first iteration of the for-loop, the value of J does not begin from 0. This means that the path followed by the algorithm is not column-by-column beginning from the first, as the above two tables suggest. For discs where there are intersection and non-intersection pairs, J follows the sorted lists, and not really the above tables. K also follows the sorted lists, but each value of K can still be imagined as representing one column of the above tables. 

When there is intersection among all the discs, the while-loop is never executed, leading to N number of iterations (operations) of the for-loop. When there is no intersection pair for all the discs, the while-loop is executed for each for-loop, leading to 2N operations (iterations). When there are some intersections and non-intersections, the total number of operations is between N and 2N. For the given problem, N is 5 and 2N is 10. So, app.codility.com/programmers gives the time complexity of the algorithm in this document as O(N) or O(N*log(N)). app.codility.com/programmers does not really take into consideration, the time spent in the sorting and previous for-loops, in order to come up with its time complexity.

The Smart Solution

And the complete code with three test cases is:

#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;

 int solution(vector<int> &A) {
    int N = A.size();
    int counter = 0;    // number of intersection pairs
    
    vector<int> left;
    for (int i=0; i<N; i++)
        left.push_back(i-A[i]);
    sort(left.begin(), left.end());
    vector<long int> right;
    for (int i=0; i<N; i++)
        right.push_back((long)i+(long)A[i]);
    sort(right.begin(), right.end());
    
    int noAddedDiscs = 1; //    assumed to start at 1
    int J=0;      
    
    for(int K=1;K<N;K++) {
        while((J<N)&&(left[K]>right[J])) {  //non-intersections 
            J++;
            noAddedDiscs--;  
        }
        
        counter += noAddedDiscs;
        if (counter>10000000) 
            return -1;
            
        noAddedDiscs++;
    }
    
    return counter;
}

Read through the whole program, if that is not already done. Note that the programmer has not defined his/her own sorting function. The output is:

    15

    0

    11 

At app.codility.com/programmers the scoring and detected time complexity for this solution() is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(N*log(N)) or O(N) 

app.codility.com/programmers took into consideration mainly the last for-loop with its nested while-loop. It did not really take into consideration, the sorts and other operations, in order to come up with its time complexity.

Chrys