Ninja and the Nested Ranges II

The idea is to use the brute force approach. For each range in the ‘RANGES’, we will check all the other ranges whether it contains some other range and if some other range contains it.

Algorithm:

• Declare a vector of vectors of integers, ‘RESULT’ to store the final result.
• Declare a vector of integers, ‘RESULT1’ of size ‘N’, where ‘RESULT1[ i ]’ will store 1 if the ‘i’th range contains some other range. Initially, fill it with zeroes.
• Declare a vector of integers, ‘RESULT2’ of size ‘N’, where ‘RESULT2[ i ]’ will store 1 if the ‘i’th range is contained by some other range. Initially, fill it with zeroes.
• Run a loop for i = 0 to N - 1.
  • Declare two integer variables, ‘X’ and ‘Y’ and assign ‘RANGES[ i ][ 0 ]’ and ‘RANGES[ i ][ 1 ]’ to them, respectively.
  • Run a loop for j = 0 to N - 1.
    • If i == j, that shows that ranges are the same. Therefore,
      • Skip the below steps.
    • Else, declare two integer variables, ‘A’ and ‘B’ and assign ‘RANGES[ j ][ 0 ]’ and ‘RANGES[ j ][ 1 ]’ to them, respectively.
    • If X <= A && Y >= B, that shows that ‘i’th range contains the ‘j’th range. Therefore,
      • Increment the ‘RESULT1[ i ]’ by 1.
    • If X >= A && Y <= B, that shows that ‘i’th range is contained by the ‘j’th range. Therefore,
      • Increment the ‘RESULT2[ i ]’ by 1.
• Push ‘RESULT1’ to the ‘RESULT’.
• Push ‘RESULT2’ to the ‘RESULT’
• In the end, return ‘RESULT’.

If the given array is sorted in ascending order by the start value of the ranges (If the start values of any two ranges are the same, then sort them in decreasing order of their end values), we can draw the following observations:

• Case 1:
  • If we traverse the array from beginning to end, any range can be contained only by any of the preceding ranges and not by the ranges after it. Also, the current range (say: ‘C’) can only be contained by any preceding ranges (say: ‘P’) if the end value of the range ‘P’ is not less than the end value of the range ‘C’. So, for any range, we can count the number of ranges preceding it having the end value greater than or equal to the end value of the range ‘C’.
• Case 2:
  • And if we traverse the array from end to the beginning, any range can only contain any of the ranges after it and not the preceding ranges. Also, the current range (say: ‘C’)  can only contain any ranges after it (say: ‘A’), if the end value of the range ‘A’ is not greater than the end value of the range ‘C’. So, for any range, we can count the number of ranges after it having the end value less than or equal to the end value of the range ‘C’.

To efficiently count the number of ranges in the above cases, we can either use a policy-based data structure in C++ like ‘ordered_set’ or a widely used data structure like Binary Indexed Trees. As both of them offer to count the number of items strictly smaller than an item ‘K’ in logarithmic time.

Given below is the implementation using ‘ordered_set’.

Algorithm:

• Include all the necessary header files, namespace and structure for the ‘ordered_set’.
• Declare a vector of vectors of integers, ‘RESULT’ to store the final result.
• Declare a vector of integers, ‘RESULT1’ of size ‘N’, where ‘RESULT1[ i ]’ will store 1 if the ‘i’th range contains some other range. Initially, fill it with zeroes.
• Declare a vector of integers, ‘RESULT2’ of size ‘N’, where ‘RESULT2[ i ]’ will store 1 if the ‘i’th range is contained by some other range. Initially, fill it with zeroes.
• Declare a vector of integers, ‘RESULT2’ of size ‘N’, where ‘RESULT2[ i ]’ will store 1 if the ‘i’th range is contained by some other range. Initially, fill it with zeroes.
• Declare a vector of an array of size 3, ‘ARR’, where the first, second and third value of the array will be the start value, end value and the index of the range present in ‘RANGES’.
• Run a loop for i = 0 to N - 1.
  • Push the start value, end value and the index of the ‘i’th range in ‘ARR’.
• Sort ‘ARR’ using a comparator function, ‘comp’.
• Declare a variable of pair of integers of ‘ordered_set’, ‘OS’.
• Run a loop for i = N - 1 to 0.
  • Declare an integer variable, ‘CONTAINEDRANGESCOUNT’ and assign ‘OS.order_of_key({ARR[i][1] + 1, -1})’, i.e., the number of ranges having the end value less than or equal to the end value of the range ‘ARR[i]’
  • Update ‘RESULT1[ ARR[ i ][ 2] ]’ by ‘CONTAINEDRANGESCOUNT’.
  • Insert ‘{ARR[i][1] + 1, i}’ in ‘OS’.
• Clear the ‘ordered_set’, ‘OS’.
• Run a loop for i = 0 to N - 1.
  • Declare an integer variable, ‘CONTAININGRANGESCOUNT’ and assign ‘i - OS.order_of_key({ARR[i][1], -1})’, i.e., the number of ranges having the end value greater than or equal to the end value of the range ‘ARR[i]’.
  • Update ‘RESULT2[ ARR[ i ][ 2] ]’ by ‘CONTAININGRANGESCOUNT’.
  • Insert ‘{ARR[ i ][ 1 ], i}’ in ‘OS’.
• Push ‘RESULT1’ to the ‘RESULT’.
• Push ‘RESULT2’ to the ‘RESULT’
• In the end, return ‘RESULT’.

Description of ‘comp’ function

This function will take two parameters:

• A1: An array of size 3 representing a range.
• A2: Another array of size 3 representing another range.

bool comp(A1, A2):

• If A1[ 0 ] == A2[ 0 ], that shows that the start values of the ‘A1’ and ‘A2’ are the same. Therefore,
  • Return A1[ 1 ] > A2[ 1 ].
• Else
  • Return A1[ 0 ] < A2[ 0 ].