PESTS - Editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: admin5
Editorialist: admin5

DIFFICULTY:

MEDIUM

PREREQUISITES:

Graph, Network Flow

PROBLEM:

You are given a grid of N X M, each cell of grid contain a number from 1 to 9, you are asked to find out the number of sequence which start from 1 and end with 9 and all numbers should be connected sequentially like 1 is directly connected to 2 and 2 is directly connected to 3 and so on.
Each block of grid can be directly connected with it’s UP , DOWN ,LEFT, RIGHT blocks .

DETAILED EXPLANATION:

You are given a N X M grid and each cell contain value from 1 to 9. In order to solve this problem you can use the concept of network flow. According to flow concept we need two more nodes source S and sink T , then we can connect each cells of grid which contain 1 to source with flow capacity of 1 because we can use each block once . And connect all cells of grid which contain 9 to sink with flow capacity of 1. And connect all intermediate node they have difference of their cell value is 1 with flow capacity of 1 like we can connect 1 with all 2’s and all 2’s with all 3’s with flow capacity of 1 and so on. Once the flow network is ready , you can apply any maximum flow algorithm to find out maximum flow of network.
Time complexity of this approach is O(N*E^2) , where E is edges in network.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

2

For clarification, how many pests are there in:

1 2 3 4
5 9 4 5
9 8 7 6

1? 2? 4? The way you’re solving it suggests that there is only meant to be one here.

3

yeah exactly!!

Is maxflow solution actually correct??

4

Yeah, in above test case there is only one pest according to problem statement.