SNSOCIAL - Editorial

bfs
easy-medium
editorial
graph-theory
snckpb17
snsocial

#1

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Hasan Jaddouh
Editorialist: Sidhant Bansal

DIFFICULTY -
Easy - Medium

PREREQUISITES -
BFS

PROBLEM -
Given a grid of n * m dimension, where the value of cell (i, j) is a*[j].

Determine the minimum no. of moves after which all the values of array a[][] will be equal given that in every move for every cell (i, j) its value a*[j] becomes the maximum of the 8 adjacent values to that cell, only if this maximum value is greater than current a*[j].

EXPLANATION -

Firstly, we can easily see that this process will end when all the values in the a[][] array have attained the maximum element of the a[][] array.

Now if we find the maximum element in the a[][] array and mark all its occurrences as SPECIAL.

The problem is reduced to this -

For each cell (i, j) we need to determine the shortest distance from cell (i, j) to any cell which is marked as SPECIAL, and the maximum of all these shortest distances is our answer. This can be done using a multi - source BFS.

This works because the shortest distance for cell (i, j) is equal to the no. of moves taken for the max value to reach cell (i, j).

Graph Theory Equivalent -

The graph theory equivalent to the above problem is this -

Given a graph with X nodes and Y edges where all the edges are bidirectional and have weight 1. Also where Z of its nodes are marked SPECIAL. Find the shortest distance of each node from any of the SPECIAL node, meaning that you have to minimise the shortest distance given that one end point is fixed as the current node and the other end point can be any SPECIAL node.

The naive method to do the above problem is to do a BFS from each SPECIAL node and then for each node determine which SPECIAL node is optimal for it depending on which SPECIAL node is nearest to it. But this solution is of the order O((X + Y) * Z), which will TLE in our case.

The faster method is to assume a fictional node W and assume that it is connected all the Z SPECIAL nodes with weight 1. Now a single BFS considering the source as W will give the answer with an extra 1 added. So subtract 1 from the shortest distances since the edge from W to the SPECIAL nodes is irrelevant. This method is commonly known as multi - source BFS as it enables us to have multiple sources. Same method can be extended to Dijkstra algorithm. This solution is fast enough and is of the order O(X + Y).

Below is a C++ implementation for better understanding -

#include "bits/stdc++.h"
using namespace std;

const int N = 505;

int a[N][N];
int dx[] = {1, 1, 1, -1, -1, -1, 0, 0}, dy[] = {1, 0, -1, 1, 0, -1, 1, -1};

bool visited[N][N];
queue<pair<pair<int, int>, int> > Q;

int n, m;

bool valid(int x, int y){
	if(x < 1 or x > n or y < 1 or y > m)	return false;
	else return true;
}

void solve(){
	int maxm = 0;

	cin>>n>>m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin>>a*[j];

			maxm = max(maxm, a*[j]);
			visited*[j] = 0;
		}
	}

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a*[j] == maxm){
				Q.push({{i, j}, 0});
				visited*[j] = 1;
			}
		}
	}

	int ans = 0;

	while(!Q.empty()){
		int x = Q.front().first.first, y = Q.front().first.second, d = Q.front().second;
		ans = max(ans, d);
		Q.pop();

		for(int i = 0; i < 8; i++){
			if(valid(x + dx*, y + dy*) == 1 and visited[x + dx*][y + dy*] == 0){
				Q.push({{x + dx*, y + dy*}, d + 1});
				visited[x + dx*][y + dy*] = 1;
			}
		}
	}	
	cout<<ans<<endl;
}

int main(){
	int t;
	scanf("%d", &t);
	while(t--)	solve();
}

Complexity -
The time complexity of a single BFS is O(no. of vertices + no. of edges in the graph) = O(n * m)

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555


#2

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class SnSocial {

public static void main(String[] args) {
    try (PrintWriter pw = new PrintWriter(System.out, false)) {
        int arr[][];
        int max = 0;
        int maxDistance = 0;
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while (t-- > 0) {
            int n = s.nextInt();
            int m = s.nextInt();
            max = 0;
            maxDistance = 0;
            List<Point> pointList = new ArrayList<>();
            arr = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr*[j] = s.nextInt();
                    if (max < arr*[j]) {
                        pointList.clear();
                        max = arr*[j];
                        pointList.add(new Point(i, j));
                    } else if (max == arr*[j]) {
                        pointList.add(new Point(i, j));
                    }
                }
            }

            for (int i = 0; i < n; i++) {
                int minDistance = 0;
                for (int j = 0; j < m; j++) {
                    if (arr*[j] != max) {
                        for (Point p : pointList) {
                            int temp = p.distance(i, j);
                            if (minDistance > temp || minDistance == 0)
                                minDistance = temp;
                        }
                        if (maxDistance < minDistance) {
                            maxDistance = minDistance;
                        }
                    }
                }
            }
            pw.println(maxDistance);
        }
    }
}

}

class Point {
int x;
int y;

Point(int x, int y) {
    this.x = x;
    this.y = y;

}

int distance(int i, int j) {
    int dis = 0;
    int hor = 0, ver = 0;
    hor = this.x - i;
    ver = this.y - j;
    if (hor < 0)
        hor = -hor;
    if (ver < 0)
        ver = -ver;
    dis = hor > ver ? hor : ver;
    return dis;

}

}
I have tried various test cases but not able to identified which could fail
Can anybody give me test cases that can be failed?


#3

I wonder where I went wrong!

program SNSOCIAL;
var T1, n, t, m, i, j, k, mx, demluot,u,v: longint;
a: array[0…501, 0…501] of longint;
b: array[0…501, 0…501] of integer;

begin
readln(T1);
for i:= 1 to T1 do
begin
readln(n, m);
mx := 0;
for j:= 1 to n do
for k:= 1 to m do
begin
read(a[j, k]);
b[j,k] := m+n;
if mx<a[j, k] then mx := a[j,k];
end;

	for j:= 1 to n do
	for k:= 1 to m do
	if(a[j, k] = mx) then
	begin 
		    b[j, k] := 0;
		    t:=1;
		    while (j-t>=1) or (j+t<=n) or (k-t>=1) or (k+t<=n) do
		    begin
		        for u:= j-t to j + t do 
		        if(u>=1) and (u<=n)then
		        begin
		            if (k-t>=1) and (t<b[u, k-t]) then b[u, k-t] := t; 
		            if (k+t<=n) and (t<b[u, k+t]) then b[u, k+t] := t;
		        end;
		        for v:= k-t to k + t do 
		        if(v>=1) and (v<=n) then
		        begin
		            if (j-t>=1) and (t<b[j-t, v]) then b[j-t, v] := t; 
		            if (j+t<=n) and (t<b[j+t, v]) then b[j+t, v] := t;
		        end;
		        t:= t+1;
		    end;
	end;
	
	demluot := 0;
	
	for j:= 1 to n do
		for k:= 1 to m do
		   if demluot < b[j,k] then demluot := b[j,k];
		
	write(demluot);
	if i<>T1 then writeln;
end;

end.


#4

The PROBLEM LINK given above is of a different problem (SNGRAPH).


#5

struct Point{
int x;
int y;
};
void changeAll(vector& tempset,int a[][500],Point p,int n,int m){
int row = p.y;
int col = p.x;
int element = a[row][col];
Point t;
if((row-1)>=0 && (col-1) >=0 && a[row-1][col-1]!=-1  && a[row-1][col-1]!=element ) // upper left corner
{
a[row-1][col-1]=element ;
t.x = col-1;
t.y = row-1;
tempset.push_back(t);
}
if(col-1 >=0 && a[row][col-1]!=-1 && a[row][col-1]!=element) // same row col -1
{
a[row][col-1]=element ;
t.x = col-1;
t.y = row;
tempset.push_back(t);
}
if((row+1) < n && (col -1) >=0&&a[row+1][col-1]!=-1  && a[row+1][col-1]!=element ) 
{
a[row+1][col-1]=element ;
t.x = col-1;
t.y = row+1;
tempset.push_back(t);
}
if((row+1) < n &&a[row+1][col]!=-1 && a[row+1][col]!=element  )
{
a[row+1][col]=element ;
t.x = col;
t.y = row+1;
tempset.push_back(t);
}
if((row+1) < n && (col +1) < m &&a[row+1][col+1]!=-1  && a[row+1][col+1]!=element )
{
a[row+1][col+1]=element ;
t.x = col+1;
t.y = row+1;
tempset.push_back(t);
}
if(col+1 < m &&a[row][col+1]!=-1 &&a[row][col+1] != element )
{
a[row][col+1] = element ;
t.x = col+1;
t.y = row;
tempset.push_back(t);
}
if((row-1) >=0 && (col+1) < m&&a[row-1][col+1]!=-1   && a[row-1][col+1]!= element)
{a[row-1][col+1] = element;
t.x = col+1;
t.y = row-1;
tempset.push_back(t);
}
if((row-1) >=0 && a[row-1][col]!=-1 && a[row-1][col] != element)
{
a[row-1][col] = element;
t.x = col;
t.y = row-1;
tempset.push_back(t);
}
return ;}
long int recur(vector tempset,int a[][500],long int c,int n,int m){
 vector::iterator it;
vector tempSet;
for(it=tempset.begin();it!=tempset.end();it++)
{Point temp = *it ;
changeAll(tempSet,a,temp,n,m);
a[temp.y][temp.x]= -1;}
if(!tempSet.empty())
{c++;
return recur(tempSet,a,c,n,m);}
else
{return c;}
}
int main(){
----input section-----
vector myset;
find max in 2D array
Point p;
for(n)for(m)
{ if(a*[j]==MAX)
{p.x = j;
p.y= i;
myset.push_back(p);
}}}
recur(myset,a,0,n,m);
print it 
--end---

I used a storage for all position of MAX in 2D array…i.e vector where location of MAXElement is stored Now iterate over its children i.e connected Points and make this Point as visited(i used -1 for that)…update this children set every time u cover all parent push tham all in vector in next iteration cover these id final set of children is empty stop recursion…Good Day…Banaji


#6

If anybody is interested in an overkill approach, I did it using binary search to set the time taken to make all numbers maximum + RMQ on 2d matrix to check for the maximum condition. You might want to have a look at this problem from JUNE16 and idea of 2d RMQ. Some optimizations will be required to pass time limit. Refer to solutions of JUNE16 CHSQARR problem or my solution.


#7

link text

giving TLE. complexity is O(n*m)


#8

The above link for practice section of problem is wrong. Here is the link for practice section of SNSOCIAL


#9

I didn’t get how they are taking another virtual node and running single BFS on it, can anyone explain it


#10

A good way to see this problem was to implement flood-fill from all the maximum points. I used the method of storing “openSet” and “closedSet” (as lists) as we do in the A* Path finding algorithm.

Initially, the openSet (the matrix positions which needs to be visited next is empty).
The closedSet contains the positions of all the maximum points.
We traverse through the closedSet and push all the non-maximum neighboring points onto the openSet (just like how we do in A* algorithm). For efficiency, we remove the points from the closedSet. (I didn’t have to maintain a closedSet since I used an auxiliary array to store all the ‘visited’ points.

Think of it as coloring the graph (flood-fill). Consider a full white colored graph. First we have some points (maximum valued). We mark these points with red color. Then we mark their non-red neighbors with grey. We get the next layer of points to be colored red. For efficiency, we mark all the currently red points with black (these are the internal points). Now, we mark the grey points with red. Now we repeat. The number of (grey) layers formed will be the answer.

![image][1]

I advise you to check out some videos on A* algorithm and know more about closedSet and openSet.

Here’s my solution:


[2]
De-comment the code to see how the flood-fill is working.


  [1]: http://i.imgur.com/HkQYvRO.jpg
  [2]: https://www.codechef.com/viewsolution/13948667

#11

What is array dx[]. I am not getting how it came ? please help


#12

i did BFS where all the elements with the maximum value are in the queue initially, that way when any node is popped off that is the minimum distance from any maximum node.


#13

A cpp solution for a starter, https://www.codechef.com/viewsolution/13920051


#14

Hello, first time i ask for advice, sorry to bother but this is driving me mad :slight_smile:

What i did:

  • loop on input, find min and max value, and storing their coordinates
  • then i test if min=max and retrun 0 if so (ie handle first test case)
  • then for each min coord, i calculate distance between this min and each max
  • then i keep the minimum of the distance found between this min and every max
  • then i do the same for every minimum
  • then i keep the maximum of the minimum found

I use distance between two coordinates = max (delta_x, delta_y)

  • because wealth propagates diagonally too
  • propagates with a cost of 1 hour each time

Here are some examples why i chose to do this instead of propagating

dx=4   dx=4   dx=4    dx=4   dx=4    dx=3    dx=2  dx=1  dx=0
dy=0   dy=1   dy=2    dy=3   dy=4    dy=4    dy=4  dy=4  dy=4
d=4    d=4    d=4     d=4    d=4     d=4     d=4   d=4   d=4
AxxxB  Axxx    Axx    Ax     A       A       A     A     A
           B      x     x     x      x       x     x     x
                   B     x     x      x      x     x     x
                          B     x      x      x    x     x
                                 B      B      B    B    B

So, my submission follows the provided explanation, except for the distance calculation explained above.

My problème is i get “Wrong Answer” and i can’t think of any flaw in what i’ve done !

I’ve made my code as clear as possible : link

Thanks in advance for any hint or test case idea


#15

Practice and contest links are for SNGRAPH.


#16

@nipil it can happen that all min points have max value but, there may be non-min points which don’t have max value.

Consider this test case:

1
2 3
2 2 4 
2 1 2

Your output: 1
Answer: 2

#17

can anybody help me where was I wrong?
https://www.codechef.com/viewsolution/13970514
Any test cases?


#18

@priyaconnect Try this test case :

1

1 3

2 1 0

Expected answer = 2
Your answer = 1
I got ac after clearing this test case.


#19

@vivekdh45
Thanks a lot…


#20

Could anyone help me in figuring out why my solution failed to accept? I used similar approach as discussed in editorial.
Link to submitted code is https://www.codechef.com/viewsolution/14017641 . Ps:- Pls provide test case.it will be more helpful.