DEFECTS - Editorial

PROBLEM LINK:

Practice
Division 1
Division 2

Author: Sachin Yadav
Tester: Taranpreet Singh
Editorialist: Sachin Yadav

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Graphs, BFS

PROBLEM:

There is a 2d grid with N rows and M columns. Each cell on the grid has some binary-integer either 0 or 1.

For making all cells in the grid same, initially we choose a cell. Now, we repeatedly apply the move on this cell, until the whole grid is filled with same binary number.

In a single move, the binary numbers in all the cells reachable from the given cell are inverted. A cell is called reachable from another cell, if both cells have the same number, and it is possible to move from one cell to the other through cells of that number only, moving vertically and horizontally. If earlier the number was 1, it turns into 0 and vice versa.

Choosing the start cell optimally, can you find the minimum number of moves to make all the cells have same number?

QUICK EXPLANATION:

We first create a condensed graph by considering cells of same number which are reachable (refer to problem statement for criteria of reachability) to one another as a single node. We number the nodes on the grid accordingly and consider the edges in the grid between different nodes to form the edges for our new graph. The answer to the problem, is the radius of this new graph formed.

EXPLANATION:

As mentioned above, we would be first converting the grid into a graph, where the cells with same number which are reachable to one another are clubbed together to form nodes for the new graph. For this we do numbering of these clusters and consider the edges between two cells with different numbering as an edge between the two respective nodes in the new graph.

Why we have converted it to a graph here? Because performing the move on any cell in the grid is equivalent to changing the colour of the node it belongs to in the new graph and merging all its immediate neighbouring nodes into it. We will be referring to this move as contracting the graph at that node to which the chosen cell corresponds.

So if we contract the graph again and again at the same node, we notice that the distance of the farthest node from the node in consideration keeps on decreasing by 1 in a single move. The corresponding grid becomes filled with same number when after contracting the graph repetitively at the same node, only a single node remains in the graph i.e. the distance of the farthest node from the chosen node in the graph becomes zero.

Hence, if we choose any node in the graph, the number of moves (contractions) it takes is equal to the distance of fartest node from the chosen node. So optimal solution comes when we choose that node whose distance to its fartest node is the least and the number of moves it takes is equal to that least distance.

So again, the solution corresponding to selecting a node is the distance of the farthest node from it. Hence the answer is the minimum among the maximum distances between the chosen node and all other nodes in the graph. This is the defintion of the radius of graph as well, so the radius of the generated graph gives solution to the problem.

Implementation

For constructing the graph from the grid there can be many approaches. What I have used is travesing over the 2d grid , flood filling the cells ,assigning them different numbers and marking them visited. For creating the adjacency list, we traverse over all the edges in the grid and add the edges to the adjacency list which are between cells of different nuberings here.
As we may be double counting the edges between two nodes several times, we can keep track by using an unordered_sets as an adjacency list. This would complete the graph formation.

We do BFS on every node to find the distance of farthest node from it.The minimum of all gives the radius of the graph.

Time Complexity: O((M\times N)^{2})

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
unordered_map<int, unordered_set<int>> adj_list;
bool is_visited[2501];
int last_vertex, N, M;
pair<bool,int> board[101][101];

int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

void bfs(int i, int j, int clr)
{
    queue<pair<int,int>> que;
    que.push({i,j});
    board[i][j].second=clr;
    while(!que.empty())
    {
        auto p=que.front();
        que.pop();
        for(int d=0; d<4; d++)
        {
            int x=p.first+dir[d][0], y=p.second+dir[d][1];
            if(x<0 || x==N || y<0 || y==M || board[x][y].second || (board[x][y].first != board[p.first][p.second].first)) continue;
            board[x][y].second=clr;
            que.push({x,y});
        }
    }
}

void get_adjlist()
{
    last_vertex=0;
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
        {
            if(board[i][j].second==0)
                bfs(i,j,++last_vertex);
        }
    
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
        {
            if(i && board[i][j].second!=board[i-1][j].second)
            {
                adj_list[board[i][j].second].insert(board[i-1][j].second);
                adj_list[board[i-1][j].second].insert(board[i][j].second);
            }
            if(j && board[i][j].second!=board[i][j-1].second)
            {
                adj_list[board[i][j].second].insert(board[i][j-1].second);
                adj_list[board[i][j-1].second].insert(board[i][j].second);
            }
        }
}


int radius_graph()
{
    int radius=2*N*M;
    for(int vtx=1; vtx<=last_vertex; vtx++)
    {
        memset(is_visited,0,sizeof(is_visited));
        queue<int> que;
        int dist=0;
        que.push(vtx);
        is_visited[vtx]=true;
        que.push(-1);
        while(!que.empty())
        {
            int curr_vtx=que.front();
            que.pop();
            if(curr_vtx==-1)
            {
                if(!que.empty()){ que.push(-1); dist++; }
                else break;
            }
            for(auto v: adj_list[curr_vtx])
            {
                if(is_visited[v]==false)
                {
                    que.push(v);
                    is_visited[v]=true;
                }
            }
        }
        radius=min(dist,radius);
    }
    return radius;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int T;  cin>>T;
    while(T--)
    {
        memset(board, 0, sizeof(board));
        cin>>N>>M;
        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                cin>>board[i][j].first;
        get_adjlist();
        cout<<radius_graph()<<"\n";
        adj_list.clear();
    }
    return 0;
}
Tester's Solution
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    //Into the Hardware Mode
    void pre() throws Exception{}
    void solve(int TC)throws Exception{
        int n = ni(), m = ni();
        hold(1 <= Math.min(n, m) && Math.max(n, m) <= 50);
        boolean[][] grid = new boolean[n][m];
        int[] set = new int[n*m];
        for(int i = 0; i< n; i++){
            for(int j = 0; j< m; j++){
                grid[i][j] = ni() == 1;
                set[i*m+j] = i*m+j;
            }
        }
        for(int i = 0; i< n; i++){
            for(int j = 0; j< m; j++){
                if(i < n-1 && grid[i][j] == grid[i+1][j])union(set, i*m+j, (i+1)*m+j);
                if(j < m-1 && grid[i][j] == grid[i][j+1])union(set, i*m+j, i*m+j+1);
            }
        }
        int[] mp = new int[n*m];
        Arrays.fill(mp, -1);
        int c = 0;
        for(int i = 0; i< n; i++){
            for(int j = 0; j< m; j++){
                int root = find(set, i*m+j);
                if(mp[root] == -1)mp[root] = c++;
                mp[i*m+j] = mp[root];
            }
        }
        int[] from = new int[c*c], to = new int[c*c];
        int cnt = 0;
        boolean[][] connect = new boolean[c][c];
        for(int i = 0; i< n; i++){
            for(int j = 0; j< m; j++){
                if(i < n-1 && grid[i][j] != grid[i+1][j]){
                    int x = mp[i*m+j], y = mp[(i+1)*m+j];
                    connect[x][y] = connect[y][x] = true;
                }
                if(j < m-1 && grid[i][j] != grid[i][j+1]){
                    int x = mp[i*m+j], y = mp[i*m+j+1];
                    connect[x][y] = connect[y][x] = true;
                }
            }
        }
        for(int i = 0; i< c; i++)
            for(int j = i+1; j< c; j++)
                if(connect[i][j]){
                    from[cnt] = i;to[cnt++] = j;
                }
        int[][] g = makeU(c, from, to, cnt);
        int ans = n*m;
        Queue<Integer> q = new ArrayDeque<>();
        for(int i = 0; i< c; i++){
            int[] di = new int[c];
            Arrays.fill(di, n*m+1);
            di[i] = 0;
            q.add(i);
            int mx = 0;
            while(!q.isEmpty()){
                int u = q.poll();
                mx = Math.max(mx, di[u]);
                for(int v:g[u]){
                    if(di[v] > di[u]+1){
                        di[v] = di[u]+1;
                        q.add(v);
                    }
                }
            }
            ans = Math.min(ans, mx);
        }
        pn(ans);
    }
    int[][] makeU(int n, int[] from, int[] to, int e){
        int[][] g = new int[n][];
        int[] cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = to[i];
            g[to[i]][--cnt[to[i]]] = from[i];
        }
        return g;
    }
    void union(int[] set, int u, int v){
        u = find(set, u);v = find(set, v);
        set[v] = u;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    long IINF = (long)1e18, mod = (long)1e9+7;
    final int INF = (int)1e9, MX = (int)2e6+5;
    DecimalFormat df = new DecimalFormat("0.0000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
    static boolean multipleTC = true, memory = false, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        if(fileIO){
            in = new FastReader("C:/users/user/desktop/inp.in");
            out = new PrintWriter("C:/users/user/desktop/out.out");
        }else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        hold(1 <= T && T <= 10);
        pre();
        for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}
 
    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }
 
        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }   
} 
3 Likes

Anyone solve this question with different approach, Please share.

1 Like

editorial is full of learning… thanks bhaiya

in this ques if we find the distinct clusters of zeros and ones and the ans will be the minimum of them as we have to change the shield that no.of times . this approach giving me a wrong ans, can anyone tell me where does this approach goes wrong.

I am doing the same approach as mentioned in the editorial that is first creating the graph of clusters of 0’s and 1’s in the grid and then to find the radius I am doing bfs from all nodes. But I am facing TLE. To avoid multiple edges I am using map. Please help
Link to my solution:
https://www.codechef.com/viewsolution/33225081

1 Like

I am doing the same approach as mentioned in the editorial but getting TLE. Please help.
Link to my solution:
https://www.codechef.com/viewsolution/39057129

I am doing the same, but getting wrong answer. Did you find out why? help me solving the problem.

my approach is to calculate the number of clusters corresponding to each number : c_0,c_1,then ans is min(c_0,c_1),it works for the sample test case,it also works for the example in the editorial, but on submission it is giving the wrong ans…

1 Like