We are given an array and numerous subarrays. What we can do is add or multiply some element to all elements of a subarray. The subarrays are given as start index and the end index. We have to find the largest number of independent subarrays from the subarrays given to us. For example:

If we have the array as given below :

$\qquad A = [a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,\dots]$

Now we are given numerous subarrays as :

$\qquad\begin{align*} S_1 &= (a_1, \dots, a_6) \\ S_2 &= (a_1, \dots, a_8) \\ S_3 &= (a_7, \dots, a_8) \end{align*}$

So in this case all manipulations that can be done by the subarray $S_2$ is actually captured by the subarrays $S_1$ and $S_3$, i.e we want to add $7$ to all elements in $S_2$ then we can do it by adding $7$ to all elements in $S_1$ and $S_3$. So $S_2$ can be removed. In this similar way we need to find out the maximum number of independent subarrays possible.

Independence here means that if any subarray can be expressed as a combination of two or more subarrays then any changes that can be made to the subarray like adding a specific element to all elements in the subarray can also be make by applying the same operation to all the subarrays which make up the given subarray. For example if we have an array of size n. Then we have a given subarray from A11(11th element) to A20(20th element) and there are two more subarrays given from A11 to A15 and A16 to A20. Then if we want to add 5 to all elements from A11 to A20. Then we can add 5 to subarray from A11 to A15 and also A16 to A20. Hence A11 to A20 is not important.

Here we just need to find the total number of independent subarrays.

  • $\begingroup$ Can you give a universal definition of "independence" here? One example is hardly sufficient. Also, this is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. $\endgroup$ – Raphael Feb 10 '14 at 11:51
  • $\begingroup$ What do you mean by "expressed as a combination of two or more subarrays"? $\endgroup$ – David Richerby Feb 10 '14 at 17:14
  • $\begingroup$ Example if we have three subarrays. First subarray starts from 1st element to 10 element of the array, second from 1st to 5th element of the array and third from 6th to 10th element of the array. So if we wish to add 7 to all elements included in the first subarray, we can add 7 to all elements in the second and third subarrays. It would cover all elements in the first subarrays. Hence first subarray is redundant. $\endgroup$ – user1580096 Feb 10 '14 at 17:46

Browse other questions tagged or ask your own question.