RISK - Editorial

editorial
, , , , , ,
8

For some reason I kept getting runtime error on first case, rest of the cases worked perfectly fine and I am unable to identify what is wrong with my solution. It would be appreciative if someone could assist.

def connected_components(board, N, M):
  visited = [[False for _ in range(M)] for _ in range(N)]
  components = []

  for i in range(N):
	for j in range(M):
		if(board[i][j] == '1' and visited[i][j] == False):
			c = []
			dfs_util(board, visited, c, i, j, N, M)
			components.append(len(c))
  components.sort(key=lambda x: -x)
  return components

def dfs_util(board, visited, c, i, j, N, M):
 if(i < 0 or j < 0 or i >= N or j >= M or board[i][j] == '0' or visited[i][j] == True):
	return

 visited[i][j] = True
 c.append([i,j])

 dfs_util(board, visited, c, i+1, j, N, M)
 dfs_util(board, visited, c, i, j+1, N, M)
 dfs_util(board, visited, c, i-1, j, N, M)
 dfs_util(board, visited, c, i, j-1, N, M)

T = int(input())
for _ in  range(T):
  N, M = map(int, input().split())
  board = []
  for i in range(N):
	row = list(input())
	board.append(row)

l = connected_components(board, N, M)

ans = 0

for i in range(len(l)):
	if(i%2 == 1):
		ans += l[i]

print(ans)
2 Likes
9

getting RE on first test case please help
#include <bits/stdc++.h>
#define rep(i, start, end) for (int i = start; i < end; ++i)
#define FASTIO
ios_base ::sync_with_stdio(false);
cin.tie(NULL)
#define vi vector
#define ll long long int
using namespace std;
long long int n, m;

bool isSafe(long long int arr[][1000000], long long int visited[][1000000], int row, int col)
{
if (row >= 0 && col >= 0 && row < n && col < m && arr[row][col] == 1 && visited[row][col] == 0)
return true;
return false;
}
int dfs(long long int arr[][1000000], long long int visited[][1000000], int row, int col,int count)
{
int rowBr[] = {0, 0, 1,-1};
int colBr[] = {1, -1, 0, 0};
visited[row][col] = 1;
for (int i = 0; i < 4; i++)
{
if (isSafe(arr, visited, row + rowBr[i], col + colBr[i]))
{
count = dfs(arr, visited, row + rowBr[i], col + colBr[i],++count);
}
}
return count;
}

vector countIS(long long int arr[][1000000])
{
vector ans;
long long int visited[n][1000000];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
visited[i][j] = 0;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j] == 0 && arr[i][j] == 1)
{

            int size = dfs(arr, visited, i, j,1);
            ans.push_back(size);
        }
    }
}
return ans;

}
int main()
{
FASTIO;
int t;
cin >> t;
while (t–)
{
cin >> n >> m;
long long int arr[n][1000000];
vector comp;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
for (int j = 0; j < m; j++)
{
if (s[j] == ‘1’)
{
arr[i][j] = 1;
}
else
{
arr[i][j] = 0;
}
}
}
comp = countIS(arr);
sort(comp.begin(), comp.end());
int sum = 0;
for (int i = comp.size() - 2; i >= 0; i -= 2)
{
sum += comp[i];
}
cout << sum << endl;
}
}

10

Even I faced the same issue. Do let me know if you found the reason for the Runtime Error

11

I am getting WA in 1, 3, and 4 cases. Please help.

#include
#include
#include
#include
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

bool inside(int i, int j, int n, int m){
return(i >= 0 and j >= 0 and i < n and j < m );
}

bool visited(int i, int j, string *m){
if(m[i][j] != ‘v’){
return false;
}
else{
return true;
}
}

bool isLand(int i, int j, string *m){
return(m[i][j] == ‘1’);
}

ll bfs(int k, int l, int r, int c, string *m){
queue <pair<int,int>> q;
ll count = 0;
if(!visited(k,l,m)){
q.push({k,l});
m[k][l] = ‘v’;
}
while(!q.empty()){
//up
pair <int,int> p = q.front();
q.pop();
count++;
int i = p.first;
int j = p.second;
if(inside(i-1,j,r,c) and isLand(i-1,j,m)){
q.push({i-1,j});
m[i-1][j] = ‘v’;
count++;
}
//right
if(inside(i,j+1,r,c) and isLand(i,j+1,m)){
q.push({i,j+1});
m[i][j+1] = ‘v’;
count++;
}
//down
if(inside(i+1,j,r,c) and isLand(i+1,j,m)){
q.push({i+1,j});
m[i+1][j] = ‘v’;
count++;
}
//left
if(inside(i,j-1,r,c) and isLand(i,j-1,m)){
q.push({i,j-1});
m[i][j-1] = ‘v’;
count++;
}
}
return count;
}

int main() {
int t;
cin >> t;
while(t–){
int n,m;
cin >> n >> m;
string mape[n];
for(int i=0;i<n;i++){
cin >> mape[i];
}
std::vector lands;

    for(int i =0; i<n;i++){
        for(int j=0;j<m;j++){
            if(mape[i][j] == '1'){
                lands.push_back(bfs(i,j,n,m,mape));
            }
        }
    }
    
    sort(lands.begin(), lands.end(), greater<int>());
    
    ll chef_land = 0;
    for(int i=1;i<lands.size();i+=2){
        chef_land += lands[i];
    }
    
    cout << chef_land << endl;
    
}
return 0;

}

12

My BFS solution

why my bfs solution is giving TLE?

where as my dfs solution is getting accepted
My DFS solution

13

You should visit an index and make increment in c when you find suitable index, and also avoid using reverse iterators for sorting as it is slower than forward iterators. There is less effect for vectors but more for maps, sets etc.

I have made some changes in your code - CodeChef: Practical coding for everyone

1 Like
14

Thank you so much for the help

15

Is incrementing c is wrong in bfs solution because i avoided the reverse iterator still it is giving tle

16

Yes, the index should be visited while pushed in queue, this is the main cause of TLE, I just mentioned about reverse iterator as additional point.

1 Like
17

oh thank you very much

18

can someone please explain why am I getting a TLE in two of the test cases ?

#include
#include
#include
#include
#include
#include
#include
typedef long long int ll;
using namespace std ;
char grid[10001][10001];
int vis[1001][1001];
int n , m ;
vector v ;
int count_1 = 0 ;
bool is_valid ( int x, int y)
{
if ( x<1 || x> n || y<1 || y >m)
{
return false ;
}
if(vis[x][y] == 1 || grid[x][y] == ‘0’)
{
return false;
}
return true ;
}
void dfs (int x , int y)
{
count_1 ++;
vis[x][y] =1 ;
if(is_valid(x, y-1))
{
dfs(x, y-1);
}
if(is_valid(x-1, y))
{
dfs(x-1,y);
}
if(is_valid(x+1, y))
{
dfs(x+1, y);
}
if(is_valid(x, y+1))
{
dfs(x, y+1);
}

}
void bfs ( int x , int y )
{

}
int main ()
{
int t ;
cin >> t ;
while (t–)
{
memset(vis, 0, sizeof(vis));
v.clear();
cin >> n >> m ;
for ( int i =1;i<=n;i++)
{
for ( int j = 1 ; j <= m ; j++)
{
cin >> grid[i][j];
}
}
for ( int i =1;i<=n;i++)
{
for ( int j = 1 ; j <= m ; j++)
{
if(grid[i][j] == ‘1’ && vis[i][j] ==0)
{
dfs(i, j);
v.push_back(count_1);
count_1 = 0 ;
}
}
}

            sort(v.rbegin(), v.rend());
            int sum  = 0;
            for ( auto it = v.begin() ; it!= v.end() ;it++)
            {
                if ((it-v.begin())%2 == 1)
                {
                sum += *it;
                }
            }
            cout << sum << endl;
        }
}
19

main crux of the problem is this line

keep capturing neighbouring cells that share a side with it if they are on land

the following test case will make it more clear

100001 // row 1
000000 // row 2
111100 // row 3
110000 // row 4
000001 // row 5

now since opponent has the first turn,
he will surely select one of the land from the bold region
once he selects one of the land from the bold region,
he easily gets neighbouring land, next-neighbouring land, next-to-next neighbouring land & so on
(by keep capturing neighbouring cells that share a side with it if they are on land 1)
hence getting 6 land-cells.

& in problem it’s mentioned about only neighbouring lands so what to do ? , believe in your fate :laughing: ?

Unfortunately, the English language is itself ambiguous (as i read in one of the software engg. books)

Hence may be this point may help
someone, who are not thinking in terms of graph,(aka considering only next neighbour)

20

Time Complexity:

Can anyone explain why its log(n.m) ?

21

can anyone tell me about my code where it is wrong .because is giving WA
here is C++ imple.
#include
#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
int m,n;
cin>>n>>m;

       int a[n+2][m+2];
       memset(a,0,sizeof(a));
       char temp;
       
       for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=m;j++)
         {
             cin>>temp;
             a[i][j]=temp-'0';
             
         }
       }
       
       
       vector<int> v;
       
       int visited[n+2][m+2];
       memset(visited,0,sizeof(visited));
       
       for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=m;j++)
           {
               if(a[i][j]==1&&visited[i][j]==0)
               {
                   visited[i][j]==1;
                   queue<pair<int,int>> q ;
                   
                   
                   pair<int,int> p;
                   p.first=i; p.second=j;
                  
                   
                   int count=0;
                   
                   q.push(p);
                   
                   while(q.size())
                   {
                     pair<int,int> pr =q.front() ;
                     
                     count++;
                     
                      q.pop();
                      
                      pair<int,int> p1;
                      
                     int x=pr.first; int y=pr.second;
                     
                     
                     if(a[x+1][y]==1&&visited[x+1][y]==0)
                     {p1.first=x+1;p1.second=y;
                         q.push(p1);
                         visited[x+1][y]=1;
                     }
                      if(a[x][y+1]==1&&visited[x][y+1]==0)
                     {p1.first=x;p1.second=y+1;
                         q.push(p1);
                         visited[x][y+1]=1;
                     }
                      if(a[x-1][y]==1&&visited[x-1][y]==0)
                     {p1.first=x-1;p1.second=y;
                         q.push(p1);
                         visited[x-1][y]=1;
                     }
                      if(a[x][y-1]==1&&visited[x][y-1]==0)
                     {p1.first=x;p1.second=y-1;
                         q.push(p1);
                         visited[x][y-1]=1;
                     }
                     
                       
                       
                   }
                   v.push_back(count);
               }
               
           }
           
       }
       
       
       sort(v.begin(),v.end());
       reverse(v.begin(),v.end());
       int ans=0;
       
      for(int i=1;i<v.size();i=i+2)
      {
          ans+=v[i];
          
      }
      
      cout<<ans<<endl;
      
      
   }
return 0;

}

22

Wrong answer on hidden test cases please help->
#include<bits/stdc++.h>
using namespace std;
int m,n;
int x,y;
vector MAP;
vector<pair<int,int>> points{{0,1},{1,0},{-1,0},{0,-1}};
bool inside(int x,int y)
{
if((x>=0 and x<m) and (y>=0 and y<n))
return true;
return false;
}
auto solution(int i,int j)
{
int count=0;
queue<pair<int,int>> q;
q.push({i,j});
MAP[i][j]=‘0’;
while(!q.empty())
{
pair<int,int> p=q.front();
q.pop();
count++;
for(pair<int,int> dest:points)
{
int xx=dest.first+p.first;
int yy=dest.second+p.second;
if(inside(xx,yy) and MAP[xx][yy]==‘1’)
{
MAP[xx][yy]=‘0’;
q.push({xx,yy});
}
}
}

return count;

}

bool comp(int a,int b)
{return a>b;}

void solve()
{
cin>>n>>m;
MAP.resize(n);
int res;
vector land;
for(int i=0;i<n;i++)
{
cin>>MAP[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(MAP[i][j]==‘1’)
{
res=solution(i,j);
land.push_back(res);
}
}
}

    int sum=0;
    sort(land.begin(),land.end(),comp);
    for(int i=1;i<land.size();i+=2)
    {
        sum+=land[i];
    }
   cout<<sum<<endl;

}
//********************************************** TEST CASES ******************************************
void testcases(int t)
{
while(t–)
{
solve();
}
}
//******************************************** MAIN FUNCTION *****************************************
int main()
{
int t;
cin>>t;
testcases(t);

}

24

The grid size is n*m hence there can be O(n \cdot m) possible connected components and sorting it would take O(n \cdot m \cdot \log{(n \cdot m)}) time.

25

Bro try to add recursion limit like

from sys import setrecursionlimit
setrecursionlimit(100000)

it will worked for me

26

Bro try to add recursion limit like in python

from sys import setrecursionlimit
setrecursionlimit(100000)

it will worked for me

27

I tried to solve this using recursion and it passed 2/4 testcases. Can anyone say why this code isnt working.

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

int n,m, cnt;
vector<vector<int>> grid;

int check(int x, int y)
{
    if(x>=n || y>=m || grid[x][y]==0)  //outside the bound
        return 0;

    grid[x][y]=0;  //removing the already checked island

    cnt=1;
    return cnt+ check(x,y+1)+ check(x+1, y);   //returns the size of the island

}

int main()
{

  int t;
  cin>>t;
  while(t--)
  {

    cin>>n>>m;

    string str;
    grid.resize(n, vector<int> (m));

    for(int i=0;i<n;i++)
    {
        cin>>str;
        for(int j=0;j<str.length();j++)
        {
           if(str[j]=='1')
                grid[i][j]=1;
            else
                grid[i][j]=0;
        }
    }

    vector<int> sizes;   //stores the sizes of all islands
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(grid[i][j]!=0)
                sizes.push_back(check(i,j));
        }
    }

    sort(sizes.begin(), sizes.end(), greater<int>());

    int sum=0;
    for(int i=0;i<sizes.size();i++)
        if(i%2==1)
            sum+=sizes[i];
    cout<<sum<<endl;

  }
  return 0;
}
28 
//

// Created by Rohit on 4/29/2021.
//
#include <bits/stdc++.h>
using namespace std;

class Game{
int row[4]={1,-1,0,0};
int col[4]={0,0,1,-1};
int n=0,m=0;
public:
int findLand(vector<vector> grid,int i,int j,vector<vector> &visited){

    //base case
    if(grid[i][j]=='0')
        return 0;

    visited[i][j]=true;
    int land=1;
    for(int k=0;k<4;k++){
        int x=i+row[k];
        int y=j+col[k];

        if(isValid(x,y) && !visited[x][y])
            land+=findLand(grid,x,y,visited);
    }
    return land;
}
bool isValid(int i,int j){
    return (i>=0) && (j>=0) && (i<n) && (j<m);
}
int playerGame(vector<vector<char>> &grid){

    n=grid.size(),m=grid[0].size();
    vector<vector<bool>> visited(n,vector<bool> (m,false));
    priority_queue<int> pq;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]=='1' && !visited[i][j]){
                int temp=findLand(grid,i,j,visited);
                pq.push(temp);
            }
        }
    }

    int p1=0,p2=0;
    bool turn =true;
    while(!pq.empty()){
        if(turn){
            p1+=pq.top();
            turn=false;
        }else{
            p2+=pq.top();
            turn=true;
        }

        pq.pop();
    }
    return p2;
}

};
int main() {

int t;
cin>>t;
while(t--)
{
    int n,m;
    cin>>n>>m;
    vector<vector<char>> grid(n,vector<char> (m,0));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>grid[i][j];

    Game g;
    cout<<g.playerGame(grid)<<endl;
}
return 0;

}

Can anyone tell me why I am getting tle?