KGP14I - Editorial

editorial
, , , ,
1

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

Editorialist’s solution