×

# KGP14I - Editorial

Editorialist: Lalit Kundu

MEDIUM

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]

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 510 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 109(enough to run in 5s).

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

# SOLUTIONS:

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,682
×1,250
×1,186
×141
×20

question asked: 25 Dec '14, 00:11

question was seen: 1,133 times

last updated: 25 Dec '14, 00:11