0 to point length. There is a sprinkler at every integer point 0, 1, ..., length, so length + 1 sprinklers in total. When switched on, the sprinkler at point i waters the segment [i - reach[i], i + reach[i]].
Switch on as few sprinklers as possible so that the whole lawn [0, length] gets watered, and return how many you used. If the lawn cannot be watered completely, return -1.
Water landing outside the lawn neither helps nor hurts.length=6, reach=[1, 0, 3, 0, 0, 1, 0] → 2
The sprinkler at point 2 waters [-1, 5] and the one at point 5 waters [4, 6]. Together they cover the whole lawn [0, 6]; no single sprinkler is enough.
length=4, reach=[1, 0, 0, 0, 1] → -1
Even with everything switched on, the stretch between points 1 and 3 stays dry.
length=3, reach=[0, 0, 5, 0] → 1
The sprinkler at point 2 alone reaches from -3 to 7.
length ≤ 10⁴len(reach) = length + 1reach[i] ≤ 100length=6, reach=[1, 0, 3, 0, 0, 1, 0]
2
Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.