Minimum Fountains

PROBLEM STATEMENT

There is a one-dimensional garden of length 'N'. On each of the positions from 0 to 'N', there is a fountain, and this fountain’s water can reach up to a certain range as explained further. In other words, there are 'N' + 1 fountains located at positions 0, 1, 2, 3, …. 'N' which can be activated in the garden.

You are given an integer 'N' and an array/list 'ARR' of length 'N' + 1, where each index of the array denotes the coverage limit of a particular fountain.

A fountain at index 'i' can water the area ranging from the position 'i' - 'ARR'['i'] to 'i' + 'ARR'['i'].

Your task is to find the minimum number of fountains that have to be activated such that the whole garden from position 0 to 'N' has access to the water from at least some fountain.

Note:

1. 0-based indexing is used in the array.
2. We only care about the garden from 0 to 'N' only. So if i - 'ARR'['i'] < 0 or i + 'ARR'['i'] > 'N', you may ignore the exceeding area.
3. If some fountain covers the garden from position 'A' to position 'B', it means that the water from this fountain will spread to the whole line segment with endpoints 'A' and 'B'.

Input Format:

The first line of the input contains an integer 'T', denoting the number of test cases.

The first line of each test case contains the integer 'N', denoting the size of the garden.

The second line of each test case contains 'N' + 1 space-separated integers denoting the array elements.

Output Format:

For each test case, print a single integer that corresponds to the minimum number of fountains to be activated.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 50
1 <= 'N' <= 10^4
1 <= 'ARR'[i] <= 'N'

Where 'ARR[i]' represents the elements at 'i'th index.

Time Limit: 1 sec

Approach 1

For every fountain, we can try to find the pair area = (left, right), where left and right are the leftmost and the rightmost index respectively where the current fountain can reach.For every index 'I' = 0 to 'I' = 'N' -1, 'LEFT' = max(0, 'I' - 'ARR'['I']) and 'right' = min('I' + ('ARR'['I'] + 1), 'N').
Now we can sort the array of pairs in non-decreasing order according to 'LEFT' to find the minimum number of fountains.
Let us create a 'DP' array of size 'N' + 1 and initialise each index to 'N' + 1 because in worst that n+1 would be the minimum number of fountains that we have to turn on and let 'DP'[0] = 0 because to cover the 0 area no fountain is required
For each of the intervals, we can use the following transition:
- For a particular index 'I' we have 2 options, either to start a new fountain or to use the previous fountain which can cover the current index.
- So we can use the following transition, For 'I' = 'AREA'[0] +1 to 'I' = 'AREA'[1] + 1, 'DP'[i] = min('DP'[i], 'DP'['AREA'[0] + 1]), where 'AREA'[0] represents the leftmost index where the current fountain can reach and 'AREA'[1] represents the rightmost index.
After the loop ends, 'DP'['N'] will contain the minimum number of fountains.

Try Problem

Approach 2

The main idea is to find the rightmost point considering each of the fountains as a starting point.
First, let us find out the range up to which the current fountain will cover.
Create a 2-D array ‘RANGES’['N'][2], where for each index ‘I’, ‘RANGES’['I'][0] will represent the leftmost index and ‘RANGES’['I'][1] will represent the rightmost index which will be covered by the current fountain.
For ‘I’ = 0 to ‘I’ = ‘N’ - 1, do the following to find the range:
- ‘IDXLEFT’ = max(0, 'I' - ‘ARR’['I'])
- 'IDXRIGHT' = min('I' + ('ARR'['I']), ‘N’).
- ‘RANGES’['I'][0] = ‘IDXLEFT’.
- 'RANGES'['I'][1] = 'IDXRIGHT'.
Let us create a map ‘max_ends’ of size ‘N’, which will contain the maximum endpoint for each starting point.
For all the pairs [left, right] in ranges:
- ‘MAXENDS’['left'] = max('MAXENDS'['left'], ‘right’).
Now we are on the final part of the solution, where we have to actually find a minimum number of fountains. Let ‘CURREND’ = -1 represent the current ending and isReachable represents the maximum reachable point from ‘currEnd’. Let count = 0 denote the minimum number of fountains.
For ‘I’ = 0 to ‘I’ = ‘N’, if ‘I’ is present in the ‘MAXENDS’, i.e. range with ‘I’ as starting point exists in ‘MAXENDS’.
- We can maximise our reach and do ‘ISRECHABLE’ = max('ISRECHABLE', ‘max_ends’['I']).
- Also if ‘I’ > ‘CURREND’, then we have to start one more fountain because the current index 'I' is greater than ‘CURREND’ so do ‘COUNT’ = ‘COUNT’ + 1 and ‘CURREND’ = ‘ISRECHABLE’.
After the loop ends if ‘ISRECHABLE’ is greater than or equal to ‘n’, then we have found the optimal answer, else we have to return -1 since there are some indexes that were not covered.