pls help with sol.
Lost Representative
Send Feedback
The Government Public School of Wadiya city is holding a congress of students. The number of representations from each grade is equal to the grade number. From the first grade, the congress has only 1 representative, from the second grade, the congress has only 2 representatives and so on and so forth. All the representatives are told to assemble in the main ground. All the same grade representatives are standing together.
A representative of grade P comes to the stage and says that he is unable to find his group of representatives. The organisers are busy with other tasks. You have to find the group for the lost representative.
The main ground is a huge N*N matrix. You are given this matrix as input. Each representative occupies a cell. An occupied cell is represented by integer 1 and an unoccupied cell by integer 0. All the representatives of the same grade are connected to each other and disconnected from other grade representatives. An occupied cell is said to be connected to those occupied cells which are reachable from its cell. A representative can move across to other occupied cells with which it shares its edges.
For example:
Alt Text
In this diagram of a part of the ground, red coloured cells represents the connected group of sixth grade students, yellow cell represents the connected group of first grade student and green represents the connected group of fourth grade students.
You will be given the matrix and you have to find the starting cell of the connected group of the lost representative.
Starting Cell is the one with the lowest row value. (If row number of two or more cells is same, then starting cell among them is the one with lowest column value)
It may be possible that the representative may be confused, and the grade he says he is from is actually not present. In that case, print starting cell as -1 -1.
Input Format:
First line of input contains integer t, representing the number of test cases.
First line of each test case contains integer n, representing the size of the matrix.
The second line onwards, the next ‘N’ lines or rows represent the ith row values.
Each of the ith rows constitutes ‘N’ column values separated by a single space.
Last line of each test case contains integer p, representing the grade of the lost representative.
Constraints:
1 <= N <= 1000
1 <= p <= 100
Output Format:
For each test case, you need to print the starting cell of the connected group of the lost representative.
Sample Input 1:
1
5
1 1 0 0 0
0 1 0 0 1
1 1 0 1 1
0 0 0 0 0
1 1 0 0 1
3
Sample Output 1:
1 4
Explanation:
The lost representative is from the 3rd grade. In the given matrix, the 3rd grade is represented by the cluster of 1s where the starting cell of this cluster is 1,4.
Beta teri id ke hisaab se tu chef ka baap hai na to bnale phir khud se. 
1 Like
Start iterating the matrix in row-major order and perform dfs for each unvisited cell. The dfs should give you the size of connected components. When the size of connected components=k, you’ve got the answer.
1 Like
Do a simple dfs and for every component store all the indices in that component in a vector, if size of the component is equals to p then sort the vector and print first value in the vector else there is no solution so print -1 -1 .
1 Like
@rohangup007 @red_rex @magdalene pls if possibly send code also
This passed away all test case?
#include<bits/stdc++.h>
#define lli long long int
using namespace std;
void dfs(lli src, vector<lli>* adj, vector<bool>& vis){
if(vis[src])
return;
vis[src]=true;
for(auto i : adj[src])
dfs(i,adj,vis);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli n,p;
cin>>n>>p;
vector<lli> adj[n];
while(p--){
lli x,y;
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<bool> vis(n,false);
lli ans=0;
for(int i=0;i<n;i++){
if(!vis[i])
dfs(i,adj,vis), ++ans;
}
cout<<ans<<"\n";
return 0;
}
This is for distinct countries qn ? But it is not working I think for
Sample Input 2:
6 4
0 1
0 2
1 2
3 4
Sample Output 2:
3
Check the solution tab.Open the test link again-they have provided solutions of all the questions
This is my ac code-
#include<bits/stdc++.h>
using namespace std;
int Safe(int arr[][1001],int row,int col,bool vis[][1001],int n){
return (row>=0)&&(row<n)&&(col>=0)&&(col<n)&&(arr[row][col]&&!vis[row][col]);
}
int DFS(int arr[][1001],int row,int col,bool vis[][1001],int &cur,int n){
static int r[]={0,0,1,-1};
static int c[]={-1,1,0,0};
vis[row][col]=true;
cur++;
for(int i=0;i<4;i++){
if(Safe(arr,row+r[i],col+c[i],vis,n))
DFS(arr,row+r[i],col+c[i],vis,cur,n);
}
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n][1001];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
cin>>arr[i][j];
}
int p;
cin>>p;
bool vis[n][1001];
memset(vis,0,sizeof(vis));
bool f=false;
int x=-1,y=-1;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(arr[i][j]==1&&!vis[i][j]){
int cur=0;
DFS(arr,i,j,vis,cur,n);
if(cur==p){
x=i;
y=j;
f=true;
break;
}
}
}
if(f)
break;
}
cout<<x<<" "<<y<<'\n';
}
return 0;
}
Sorry, my bad. Here’s my code for this question. Although the other code passed all tc for country group question.
#include<bits/stdc++.h>
using namespace std;
void dfs(int i, int j, vector<vector<int>>& arr, vector<vector<bool>>& vis, int& size){
if(i<0 || j<0 || i>=arr.size() || j>=arr[0].size() || arr[i][j]==0 || vis[i][j])
return;
vis[i][j]=true;
++size;
dfs(i-1,j,arr,vis,size);
dfs(i+1,j,arr,vis,size);
dfs(i,j-1,arr,vis,size);
dfs(i,j+1,arr,vis,size);
}
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
vector<vector<int>> arr(n,vector<int>(n));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>arr[i][j];
int p;
cin>>p;
bool flag=0;
vector<vector<bool>> vis(n,vector<bool>(n,false));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(arr[i][j]==1 && !vis[i][j]){
int s=0;
dfs(i,j,arr,vis,s);
if(s==p){
cout<<i<<" "<<j<<"\n";
flag=true;
}
}
}
if(flag)
break;
}
if(!flag)
cout<<"-1 -1\n";
}
return 0;
}
2 Likes