ROCBOMB - Editorial


ROC Finals

Author: Ved Bhatawadekar
Tester: Ajinkya Kharosekar
Editorialist: Ved Bhatawadekar




Greedy, DP


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,

  1. Cities which it will affect (all cities in rectangle bound by x1, y1 and x2, y2

  2. Probability of that bomb being dropped.

You have to calculate the expected value of the damage after all such q bombs.


Note that element in the grid is not necessarily 1. Thus, we cannot calculate sum of subarray by taking product its length and breadth.



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).


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).


O(n x m+ q )


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):
            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]
                ans += p*(pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1])