You are not logged in. Please login at to post your questions!


KGP14I - Editorial



Editorialist: Lalit Kundu






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


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
    //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

    for j=0 to m[i]:

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.


Editorialist's solution

This question is marked "community wiki".

asked 25 Dec '14, 00:11

darkshadows's gravatar image

5★darkshadows ♦
accept rate: 12%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 25 Dec '14, 00:11

question was seen: 1,133 times

last updated: 25 Dec '14, 00:11