FastPrep
Problem · Dynamic Programming

Smart Gardener (Intuit India)

● HardIntuitINTERNOA

Sam the gardener takes care for the garden in his area. One of the jobs in the garden is to water the garden. The garden has attached equidistant sprinklers, where each sprinkler has a range and a cost associated with it. Sam wants to switch on the sprinklers in such a way that whole garden is watered and the cost of this operation is minimised, so that he can use the money in some other gardening activities.

Can you help Sam in optimising the cost of watering the garden?

We can assume the garden to be on a x axis, where sprinklers are placed on every integer index from 0 to length of the garden. So, if the len of garden is n, then it has n + 1 sprinkles from 0 to n. If it is not possible to water the garden then return -1.

A sprinkler placed on index i with range r can water the garden from i-r to i+r.

Input Format

  • First line contains single integer N denoting the len of the garden.
  • Second line contains N + 1 space separated integers denoting the range of N + 1
  • Third line contains N + 1 space separated integers denoting the cost of N + 1 sprinkles

    • Output Format

  • Min cost of watering the garden

    • Examples
    01 · Example 1
    n = 4
range = [0, 0, 0, 0, 0]
cost = [1, 2, 3, 4, 5]
return = -1
    No explanation is provided for now...
    02 · Example 2
    n = 4
range = [1, 1, 2, 1, 0]
cost = [5, 2, 5, 1, 1]
return = 3
    No explanation is provided for now...
    Constraints
  • 1 <= N <= 10^4
  • 0 <= range[i] <= 100
  • 0 <= cost[i] <= 10^4
    • More Intuit problems
    drafts saved locally
    public int minCostToWaterGarden(int n, int[] range, int[] cost) {
    // write your code here
}
    n4
    range[0, 0, 0, 0, 0]
    cost[1, 2, 3, 4, 5]
    expected-1
    sign in to submit