MARLA - Editorial

editorial
, , , , , , ,
1

PROBLEM LINK:

Practice Link

Contest Link

Author: Ankush Khanna

DIFFICULTY:

Easy

PREREQUISITES:

DFS, BFS

PROBLEM:

Given an N \times M grid, filled with integers, find the largest connected area (side adjacent elements) filled with same numbers. If there are more than one such connected areas, find the one filled with the minimum number. Print the Value and Area of that region.

QUICK EXPLANATION:

Key to AC: Run a Depth First Search on the elements of the grid to find the various connected components, and then just find the one with maximum elements connected, if there are more than one such areas, find the one with minimum number written on them.

EXPLANATION:

To solve this problem, one needs to know about what connected components are. And the best approach would be a DFS through the grid to find all connected components in this grid (connected in a sense that same elements which are side adjacent are parts of one single component). To find the region with the maximum number of elements is just an added task here, we just need to keep a track of it, that’s it. Moreover, finding the region with largest area (number of elements) and having the least possible element value if there exist more than one regions with the maximum area, is another added task.

Almost all the solutions that achieved only 30 points (sub-task 1), either missed on some edge cases, failed to keep track of optimal region correctly, or were unable to control recursion for their recursive DFS implementation (improper user of the visited nodes).

This problem can easily be solved in O(N \times M) time with O(N \times M) auxiliary space for keeping a track of the visited nodes, just to control excessive recursion (for recursive approaches) or excessive searching (for iterative approaches).

This problem is very similar to the Number of Islands problem, the difference here is just that here we need to keep a track of the area and value involved for a particular region found. Also, a similar problem is the Largest Region problem.

COMPLEXITY:

O(N \times M) time with O(N \times M) auxiliary space.

SOLUTION:

Setter’s Solution [Plain Text]

RELATED PROBLEMS:

Number of Islands Problem

Largest Region Problem

Two Flowers (This one is way more complex because it involves DSU, as we can have at most two different numbers in a region, a very good problem to practice).

Feel free to share your approach. If you have any queries, they are always welcome.

2 Likes
2

Hello, can someone please help me where am I going wrong:
https://www.codechef.com/viewsolution/32032103

3

Actually you need to change the line 10 of your code to this:

visited = [[False for _ in range(m) ] for _ in range(n)]

You need to have a grid with M columns and N rows, while you currently have written N columns and M rows for your visited grid, which is actually raising an index out of range runtime exception in your dfs code at line 5.

Hope it helps!

1 Like
4

Thanks a lot man, that was my bad. But still I am failing at TC #9 under sub task #2
https://www.codechef.com/viewsolution/32034283
Will you please help me, I am getting wrong only on one TC.

6

We haven’t made any non-trivial changes.
Can you provide a submission link which had got AC in the recent past, but gets RE on submitting the same code now?

1 Like
7

Oh I am sorry. It was my bad. I should’ve looked more closely. It is all fine from CodeChef’s end.

8

First of all you should set your Python recursion limit to some large number, as the tests are large in sub task 2 (1 \leq N \times M \leq 10^{6}), and Python’s default recursion limit is 10^{3}. This can be done easily by the following code:

from sys import setrecursionlimit

setrecursionlimit(10**9) # Or some other large number

But again, as the time limit for this problem is very tight, Python, probably, is not the right tool to solve it. It is an interpreted language and is very slow on recursion. During this contest, there wasn’t any 100 point Python submission. There is only one 100 point Python submission, and that too in the practice section. It contains a non-recursive DFS implementation.

This is a Python3 solution by @kkoder_1729 : CodeChef: Practical coding for everyone

You can have a look at it.
Hope it helps!

1 Like
9

Thank you so much for the help man :slight_smile:

11

Can anybody help me where am I going wrong? I’m getting wrong answer in two testcases for the original constraints. Below is the link to my solution:
https://www.codechef.com/viewsolution/33200381

12

Cannot view the solution since it is a contest

13

These problems are available in practice section also, and CodeChef DSA Learning Series is meant for Educational Purpose only. So you can share your approach or code from the practice section also. Or you can read the editorial or refer to an AC solution for more help.

14

can you please help me …i am getting wa on some testcases…but i dont know why
here is the link of my solution
https://www.codechef.com/viewsolution/34206931

15

Your solution is not visible to others, it might be from the DSA contest. You can try the problem in the practice section here. Also, you can check others’ solutions from the practice section for more clarity.

16

36205845
Why I am getting WA in last two test cases in original constraints in above solution ?

17

Your DFS method is incorrectly implemented. You are not checking all the adjacent values. Here’s a counter case where your DFS will fail:

3 3
1 2 1
2 2 2
1 2 1

Your solution will give the output as:

2 4

While the correct answer is:

2 5

(Specifically, you’re not checking elements onto the left side of a position).

Hope it helps!

18

got it. Thanks