### PROBLEM LINK:

**Editorialist**: Lalit Kundu

### DIFFICULTY:

MEDIUM

### PRE-REQUISITES:

Maths

### PROBLEM:

**S** sprinklers spread across a **K * K** matrix(where each cell when irrigated gives a certain profit, defined by the profit matrix).

Each sprinkler to be assigned a value **val***(which denotes the area around it which it can irrigate). Maximise the profit with respect to these constraints:

**A.** Sum of **val*** for all sprinklers shouldn’t exceed **C**.

**B.** 0 ≤ **val*** ≤ **m***

##Constraints:

**S, K ≤ 10**

* 0 < m ≤ 4**

**0 < C ≤ 20**

### EXPLANATION:

This was probably not intended as a hard algorithm problem but more of a implementation and complexity analysis problem.

Let’s generate all possible ways of generating the **val** array and then for each possible way check the profit we’ll get overall.

How do we generate all possible ways? Backtracking! Now, here’s when recursion comes into play.

```
//denotes we are assigning values to i'th index
backtrack(i):
//we have assigned everyone some values
if i==s+1:
sum = total sum of val array
if sum > c: return
profit = get total profit with current assignment
ans=max(ans,profit)
return
for j=0 to m*:
val*=j
backtrack(i+1)
```

Now comes the next step of calculating profit we get with a certain assignment.

For each sprinkler, we mark all cells/plots that it covers and then in two loops of order K, we add to our current profit the profit of marked cells. Complexity here would be * O(S*summation{m^{2}} + K*K)**.

Another way would be for each pair of (cell, sprinkler) check if that sprinkler irrigates that cell(mark if it can). Complexity here would be **O(S*K*K + K*K). This approach is supposed to timeout.

##Complexity Analysis

Worst case we’ll be generating **5 ^{10}** states and for each state we’ll calculate the profit.

So, overall complexity would be

*O(product{m*} * {S*summation{m^{2}} + K*K})*

*. Considering that we’ll ignore profit calculation for all those cases where*exceeds

*summation{m*}**C**, the worst case complexity won’t be higher than

**10**(enough to run in 5s).

^{9}See editorialist’s solution for implementation if you still face problems.