# PROBLEM LINK:

Practice

Contest

**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[i]**(which denotes the area around it which it can irrigate). Maximise the profit with respect to these constraints:

**A.** Sum of **val[i]** for all sprinklers shouldn't exceed **C**.

**B.** 0 ≤ **val[i]** ≤ **m[i]**

## Constraints:

**S, K ≤ 10**

**0 < m[i] ≤ 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[i]:
val[i]=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[i]**^{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[i]} * {S*summation{m[i]**^{2}} + K*K}). Considering that we'll ignore profit calculation for all those cases where **summation{m[i]}** exceeds **C**, the worst case complexity won't be higher than **10**^{9}(enough to run in 5s).

See editorialist's solution for implementation if you still face problems.

# SOLUTIONS:

Editorialist's solution

asked
**25 Dec '14, 00:11**

5★darkshadows ♦

3.0k●93●164●187

accept rate:
12%