MDSC - Editorial

general
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Md Shahid

Tester: Arkapravo Ghosh

Editorialist: Md Shahid

DIFFICULTY:

EASY

PREREQUISITES:

Matrix, Dynamic programming

PROBLEM:

You have given two matrix, one is binary matrix and another is weight matrix.

  • Binary matrix represents on which block you can step forward like you can only step upon block having zero.
  • Weight matrix represents weights of each block

You need to find the minimum possible weighted path sum if present.

EXPLANATION:

Before we get into the problem, i want to introduce you a dynamic programming technique which you may or may not know.We will understand in following ways-

  1. Algorithm (Path in a grid)
  2. Problem Solution

1. Path in a grid

Suppose you have matrix of size N x$N$. Each of the cell of matrix has a number assigned to it. Your task is to find the sum of path from position (1,1) to (N,N) such that sum is maximum possible. But there is one condition that you can only move down and right. For example -

3 2 1 0
5 8 9 1
0 1 10 11
11 12 15 5

In this case, the maximum possible distance is 55. The following describes the path on which we can get maximum possible sum.

3
5 8 9
10
15 5

1.1 Algorithm

Assume that the rows and columns of the grid are numbered from 1 to n, and value[y][x] equals the value of cell (y, x). Let sum(y, x) denote the maximum sum on a path from the upper-left corner to cell (y, x). Now sum(n,n) tells us the maximum sum from the upper-left corner to the lower-right corner. For example, in the above grid, sum(4,4) = 55.

We can recursively calculate the sums as follows:

sum(y, x) = max(sum(y, x−1),sum(y−1, x))+value[y][x]

The recursive formula is based on the observation that a path that ends at
square (y, x) can come either from square (y, x−1) or square (y−1, x)

Thus, we select the direction that maximizes the sum. We assume that
sum(y, x) = 0 if y = 0 or x = 0 (because no such paths exist), so the recursive
formula also works when y = 1 or x = 1.

Steps

  • Initialized sum[N+1][N+1] = {0}
  • Run a For loop fron i = 1 to i = N
  • Again run a For loop fron j=1 to j=N
  • sum(i, j) = max(sum(i, j−1),sum(i−1, j))+value[i][j]
  • End For
  • End For
  • Return sum[N][N]

2. Problem Solution

Problem can be solved in following steps:

  1. Check the possibility.

  2. Find maximum possible path sum.

2.1 Check the possibility:

In first step you have to invert all the bits of your binary array. Inverting bits means, you have to make all zero to one and all one to zero. For example-

Suppose you have binary matrix b[N][N] -

0 0 1 1
0 0 0 1
1 1 0 0
0 1 0 0

Inverted form $b[N][N]$

1 1 0 0
1 1 1 0
0 0 1 1
1 0 1 1

Reason for inverting the b[N][N] matrix is, we can apply recursive algorithm to check there exists a path or not.

2.1.1 Algorithm

  • Initialized valid[N+1][N+1] = {0} and valid[0][1] = valid[1][0] = 1
  • Run a For loop fron i = 1 to i = N
  • Again run a For loop fron j=1 to j=N
  • valid[i][j] = (valid[i-1][j] || valid[i][j-1]) && b[i][j]
  • End For
  • End For
  • Return valid[N][N]

If the value of valid[N][N] is 1 i.e, there exist at least one path.

2.2 Find maximum possible path sum:

If the value of valid[N][N] is 1 i.e, there exist at least one path. If there exists path then run the recursive algorithm which is stated earlier to find maximum path sum keeping the track of b[N][N] matrix.

2.2.2 Algorithm

  • Initialized dis[N+1][N+1] = {0}
  • Run a For loop i = i to i = N
  • Run another loop j = 1 to j = N
  • If valid[i][j] == 1
  • dis[i][j] = min(dis[i-1][j], dis[i][j-1]) + a[i][j] (where a is weight matrix)
  • End If
  • End For
  • End For
  • Print “Yes” and dis[N][N].

Complexity :

The time complexity of this algorithm is O(N^2) and space comlexity is O(N^2).

AUTHOR’S AND EDITORIALIST’S SOLUTIONS:

Author’s and editorialist’s solution can be found here.

1 Like