PROBLEM LINK:
Author: Ved Bhatawadekar
Tester: Ajinkya Kharosekar
Editorialist: Ved Bhatawadekar
DIFFICULTY:
MEDIUM
PREREQUISITES:
Greedy, DP
PROBLEM:
A country can be represented as a grid of n rows and m columns where there are total n∗m cities. These cities are about to face bomb attacks. There are q such bombs and we know the probability of each bomb attack and on which cities will it affect. You have given x1, y1 and x2, y2 and the probability of a drop of bomb. The bomb will affect all the cities in rectangle bound by x1, y1 and x2, y2. If a bomb attacks happens of a particular city it does probability of bomb ∗ D(i,j) damage to the country where D is the matrix which contains the damage the country will get if that city gets hit by bomb. You know the following information about bombing,
-
Cities which it will affect (all cities in rectangle bound by x1, y1 and x2, y2
-
Probability of that bomb being dropped.
You have to calculate the expected value of the damage after all such q bombs.
QUICK EXPLANATION:
Note that element in the grid is not necessarily 1. Thus, we cannot calculate sum of subarray by taking product its length and breadth.
EXPLANATION:
SUBTASK:
Take the sum of elements in the subarray in O(n*m) for each query.
Then multiply it by the probability and add to the answer. This is the brute-force approach which has complexity of
O(q x n x m).
TASK:
It is a 2D version of prefix array. We calculate pre[i][j] = pre[j-1][k]+pre[j][k-1]-pre[j-1][k-1]+grid[j-1][k-1]
where pre[i][j] denotes the sum of values in a rectangular subarray from the upper left corner to the position of [i][j].
The sum of the grey subarray can be calculated using the formula S(A)− S(B)− S( C)+ S(D)
where S(X) denotes the sum of values in a rectangular subarray from the upper left corner to the position of X
For each query we can now find the sum in the subarray in O (1).
COMPLEXITY
O(n x m+ q )
SOLUTIONS:
Setter's Solution
n,m = map(int,input().split())
grid = []
for j in range(n):
grid.append([int(x) for x in input().split()])
q = int(input())
bombs = []
for j in range(q):
bombs.append([float(x) for x in input().split()])
pre = []
for j in range(n+1):
row = []
for k in range(m+1):
row.append(0)
pre.append(row)
for j in range(1,n+1):
for k in range(1,m+1):
pre[j][k] = pre[j-1][k]+pre[j][k-1]-pre[j-1][k-1]+grid[j-1][k-1]
# for row in pre:
# print(row)
ans = 0
for bomb in bombs:
x1 = int(bomb[0])
y1 = int(bomb[1])
x2 = int(bomb[2])
y2 = int(bomb[3])
p = bomb[4]
#print(pre[x2][y2],pre[x1-1][y2],pre[x2][y1-1],pre[x1-1][y1-1])
ans += p*(pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1])
print(ans)