Tony_Kakkar's blog

By Tony_Kakkar, history, 6 weeks ago, In English

problem link

Can anyone offer suggestions on how to tackle this problem?

PS: This came in an online assessment of Uber (India)

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

Observe that any two nodes connected by an edge must belong to group with different parity (odd or even). So, if the graph has odd cycles, the answer doesn't exist.

Secondly, observe that if a node $$$i$$$ belongs to group $$$1$$$, all its neighbours must belong to group $$$2$$$. I can safely replace the group of node $$$i$$$ with group $$$3$$$. It won't make a difference. So, WLOG I can say that there is exactly $$$1$$$ node which belongs to group $$$1$$$.

Next, fix a node $$$j$$$ belonging to group $$$1$$$. Then, imagine assigning groups to nodes in increasing order. This seems similar as BFS! So, start a BFS with node $$$j$$$, and whenever you reach an unvisited node, just assign it the appropriate group number, more formally, if you reach unvisited node $$$u$$$ via node $$$v$$$, then assign the group of node $$$u$$$ as $$$g[v] + 1$$$, where $$$g[i]$$$ denotes group of node $$$i$$$, finally take the maximum group number among all the possible starting node $$$j$$$.
Complexity: $$$O(N*(N+M))$$$ where, $$$N$$$ is the no. of nodes and $$$M$$$ is the number of edges.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    #include <bits/stdc++.h>
    using namespace std;
    int G[1001][1001];
    
    bool checkOddCycle(int src, int V){
        int colorArr[V];
        for(int i=0;i<V;i++){
            colorArr[i]=-1;
        }
        colorArr[src]=1;
        queue<int> q;
        q.push(src);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            if(G[u][u]==1){
                return true;
            }
            for(int v=0;v<V;v++){
                if(G[u][v]==1 && colorArr[v]==-1){
                    colorArr[v]=1-colorArr[u];
                    q.push(v);
                }
                else if(G[u][v]==1 && colorArr[v]==colorArr[u]){
                    return true;
                }
            }
        }
        return false;
    }
    
    int findX(int n){
        if(checkOddCycle(0,n)==true){
            return -1;
        }
        int res=0;
        for(int i=0;i<n;i++){
            vector<int> group(n,0);
            vector<bool> vis(n,false);
            queue<int> q;
            q.push(i);
            group[i]=1;
            vis[i]=true;
        
            while(!q.empty()){
                int size=q.size();
                while(size--){
                    int node=q.front();
                    q.pop();
                    for(int nei=0;nei<n;nei++){
                        if(G[node][nei]==1 && vis[nei]==false){
                            q.push(nei);
                            vis[nei]=true;
                            group[nei]=group[node]+1;
                        }
                    }
                }
            }
            res=max(res,*max_element(group.begin(),group.end()));
        }
        return res;
    }
    
    int main() {
        memset(G,0,sizeof(G));
        G[0][8]=1;
        G[0][1]=1;
        G[0][6]=1;
        G[0][3]=1;
        
        G[1][2]=1;
        G[1][0]=1;
        
        G[2][6]=1;
        G[2][1]=1;
        
        G[3][4]=1;
        G[3][7]=1;
        G[3][0]=1;
        
        G[4][8]=1;
        G[4][5]=1;
        G[4][3]=1;
        
        G[5][4]=1;
        G[5][7]=1;
        
        G[6][0]=1;
        G[6][2]=1;
        G[6][7]=1;
        
        G[7][3]=1;
        G[7][6]=1;
        G[7][5]=1;
        
        G[8][4]=1;
        G[8][0]=1;
        cout<<findX(9)<<endl;   // ANSWER=4 (OUTPUT) 
     /*----------------------------------------------------------*/   
        
        memset(G,0,sizeof(G));
        G[0][1]=1;
        G[1][0]=1;
        cout<<findX(2)<<endl;   // ANSWER=2 (OUTPUT)
    /*----------------------------------------------------------*/   
        
        memset(G,0,sizeof(G));
        G[0][1]=1;
        G[0][2]=1;
        
        G[1][0]=1;
        
        G[2][0]=1;
        cout<<findX(3)<<endl; 
     /*----------------------------------------------------------*/  
        
        memset(G,0,sizeof(G));
        G[0][1]=1;
        G[0][2]=1;
        G[0][3]=1;
        
        G[1][0]=1;
        G[1][2]=1;
        G[1][3]=1;
        
        G[2][0]=1;
        G[2][1]=1;
        G[2][3]=1;
        
        G[3][0]=1;
        G[3][1]=1;
        G[3][2]=1;
        cout<<findX(4); // ANSWER=-1 (OUTPUT) 
        return 0;
    }
    
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Its too blurry, the condition part. Please can you clear that

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We are given N cities and M bridges, each bridge connects two cities where it is possible to travel from any one city to any other city using a sequence of bridges.

    We want to divide these N cities into X disjoint groups G1, G2....Gx such that any one of the following conditions meet for any bridge that connects two cities A and B:

    if A belongs to Gi then B belongs to Gi+1 (1 <= i <= x-1) if A belongs to Gi then B belongs to Gi-1 (2 <= i <= x) Find the maximum value of X, or print -1 if such division is impossible

    Constraints 2 <= N <= 250

    Input Format

    First line contains N, an integer N line follows, one for each city, ith line contains N characters , where the jth character is 1 if there is a bridge between city i and j, else the character is 0

    Sample Input 1

    4 0111 1011 1101 1110

    Sample Output 1

    -1

    Explanation It is not possible to divide the cities into different groups by following the given constraints

    Sample Input 2

    2 01 10

    Sample Output 2

    2

    Explanation City 1 can be in 1st group and city 2 can be in 2nd group, hence, max value of x is 2

    Sample Input 3

    3 011 100 100

    Sample output 3

    3

    Explanation City 2 can be in 1st group, city 1 can be in 2nd group and city 3 can be in 3nd group, hence, max value of x is 3

    [execution time limit] 3 seconds (java)

    [input] integer n

    [input] array.array.char mat

    N line follows, one for each city, ith line contains N characters , where the jth character is 1 if there is a bridge between city i and j, else the character is 0

    [output] integer