RISK - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Akash Bhalotia
Tester: Felipe Mota
Editorialist: Vichitr Gandas

DIFFICULTY:

EASY

PREREQUISITES:

DFS, BFS, Connected Components

PROBLEM:

Given a binary grid. 1 shows land and 0 shows water.
In a turn, a player can capture an uncaptured cell that has land, and keep capturing neighboring cells sharing a side if they are also land. The game continues till no uncaptured cell has land and each player wants to capture as big size of land as possible in total when the game finishes. Find the maximum size of land that Chef can capture (in number of cells) if he plays second, and both players play optimally.

QUICK EXPLANATION:

Run BFS or DFS and find sizes of all connected components with all ones. Sort the sizes array in decreasing order. Finally find the sum of alternate elements starting from index 1.

EXPLANATION:

In each turn, one player can start capturing a cell with value 1 and he will keep capturing until he keeps finding 1. So basically, the player captures one whole connected component in one turn.

As both players play optimally, first player will always try to get bigger components, similarly the second player. Hence largest component will be captured by first player, second largest by second player, third largest by first player again, fourth largest by second player again and so on.

Hence we can find the sizes of all connected components with all ones. And sort the size array in decreasing order. Then find sum of alternate elements starting with index 1. (Assuming 0-based indexing). This will give us the total sum, second player can achieve.

TIME COMPLEXITY:

O(n \cdot m \cdot \log{(n \cdot m)}) per test case

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define pb push_back 
#define ll long long int
#define pii pair<int, int>

using namespace std;
  
const int maxn = 1e5;
const int maxm = 1e5;
const int maxtnm = 1e6;
int del[][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int main()
{ 

    int t, tot = 0; cin >> t;
    while(t--){
        int n, m; cin >> n >> m; tot += n * m;
        vector<string> v; v.clear();
        bool visit[n][m]; 
        string s;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                visit[i][j] = false; 
            }
            cin >> s;
        	v.pb(s);
        }
        int queue[n * m], now = 0, end = 0; 
        int comp = 0, cnt = 0;
        vector<int> arr; arr.clear();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(visit[i][j] || !(v[i][j] - '0'))continue;
                comp++; cnt = 0;
                queue[end++] = m * i + j; visit[i][j] = true;
                while(now < end){
                    cnt++;
                    int u = queue[now];
                    int nj = u % m, ni = u / m;
                    for(int k = 0; k < 4; k++){
                        int ui = ni + del[k][0], uj = nj + del[k][1];
                        if(ui >= n || uj >= m || ui < 0 || uj < 0)continue;
                        if(visit[ui][uj] || !(v[ui][uj] - '0'))continue;
                        queue[end++] = m * ui + uj; visit[ui][uj] = true;
                    }
                    ++now;
                }
                arr.pb(cnt);
            }
        }
        sort(arr.begin(), arr.end(), greater<int>());
        assert(arr.size());
        int ans = 0;
        for(int i = 1; i < arr.size(); i += 2){
            ans += arr[i];
        }
        cout << ans << endl;
    }
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
struct union_find {
    vector<int> parent;
    int n;
    union_find(int n) : n(n) { clear(); }
    inline void clear(){ parent.assign(n, -1); }
    inline int find(int u){ return (parent[u] < 0) ? u : parent[u] = find(parent[u]); }
    inline bool same(int u, int v){ return find(u) == find(v); }
    inline bool join(int u, int v){
        u = find(u);
        v = find(v);
        if (u != v){
            if (parent[u] > parent[v])
                swap(u, v);
            parent[u] += parent[v];
            parent[v] = u;
        }
        return u != v;
    }
    inline int size(int u){ return -parent[find(u)]; }
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = readIntLn(1, 100000); // ????
	int sum_nm = 0;
	while(t--){
		int n = readIntSp(1, TEN(5)), m = readIntLn(1, TEN(5));
		sum_nm += n * m;
		int q1 = 0;
		vector<string> grid(n);
		for(int i = 0; i < n; i++){
			grid[i] = readStringLn(m, m);
			for(auto & c : grid[i])
				assert(c == '0' || c == '1');
			q1 += count(grid[i].begin(), grid[i].end(), '1');
		}
		assert(q1 > 0);
		union_find uf(n * m);
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				for(int di : {0, 1})
					for(int dj : {0, 1})
						if(abs(di) + abs(dj) == 1){
							int ni = i + di, nj = j + dj;
							if(ni >= 0 && ni < n && nj >= 0 && nj < m){
								if(grid[i][j] == grid[ni][nj]){
									uf.join(i * m + j, ni * m + nj);
								}
							}
						}
		vector<int> szs;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				if(grid[i][j] == '1' && uf.find(i * m + j) == i * m + j){
					szs.push_back(uf.size(i * m + j));
				}
		sort(szs.rbegin(), szs.rend());
		int ans = 0;
		for(int i = 1; i < szs.size(); i += 2)
			ans += szs[i];
		cout << ans << '\n';
	}
	assert(sum_nm <= TEN(6));
	assert(getchar() == -1);
	return 0;
}
Editorialist's Solution
/***************************************************

@author: vichitr
Compiled On: 23 Apr 2021

*****************************************************/
#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define int long long
// #define double long double
#define pb push_back
#define pf pop_front
#define mp make_pair
#define ip pair<int, int>
#define F first
#define S second

#define loop(i,n) for(int i=0;i<n;i++)
#define loops(i,s,n) for(int i=s;i<=n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
// using namespace __gnu_pbds;
// typedef tree<ip, null_type, less_equal<ip>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

const ll MOD = 1e9+7;
const ll SZ = 107;
const ll N = 1e6+7;
const ll M = 1e4+7;

int n, m, c; 

void dfs(int x, int y, vector<string> &g, vector<vector<bool>> &vis){
    if(x < 0 or x >= n or y < 0 or y >= m or vis[x][y] or g[x][y] == '0')
        return;
    vis[x][y] = 1;
    c++;
    dfs(x-1, y, g, vis);
    dfs(x+1, y, g, vis);
    dfs(x, y-1, g, vis);
    dfs(x, y+1, g, vis);
}

void solve(){
    cin>>n>>m;
    vector<string> g(n);
    vector<vector<bool>> vis(n, vector<bool>(m, 0));
    loop(i, n) cin >> g[i];
    vector<int> comps;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!vis[i][j]){
                c = 0;
                dfs(i, j, g, vis);
                comps.pb(c);
            }
        }
    }
    sort(comps.begin(), comps.end());
    reverse(comps.begin(), comps.end());
    int ans = 0;
    for(int i=1;i<comps.size(); i+=2)
        ans += comps[i];
    cout << ans << '\n';
}

signed main()
{
    // fast;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    
    
    int t=1;
    cin >>t;
    for(int i=1;i<=t;i++)
    {
        // cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}

4 Likes

My Python implementation for DFS not working for 2 cases .Why?

from sys import setrecursionlimit
setrecursionlimit(10**8)

def dfs(x,y,mat):

if x >=N or y >= M:
    return 0

if mat[x][y] != '1':
    return 0

if vis[x][y]:
    return 0

vis[x][y] = True

return dfs(x+1,y,mat) + dfs(x,y+1,mat) + 1

def func(mat):
sc = []
ans = 0

for i in range(N):

    for j in range(M):

        if mat[i][j] == '1':

            if not vis[i][j]:
                sc.append(dfs(i,j,mat))


sc.sort(reverse=True)

for i in range(1,len(sc),2):
    ans += sc[i]

return ans

for t in range(int(input())):

N,M = map(int,input().split())
mat = []
vis = [[False for i in range(M)] for j in range(N)]

for i in range(N):
    mat.append(list(input()))

#print(mat)

print(func(mat))

I think you should do
return dfs(x+1,y,mat) + dfs(x,y+1,mat) +dfs(x-1,y,mat) + dfs(x,y-1,mat) + 1
And remember modify the exit condition.

3 Likes

It worked .Thanks

Can somebody tell me why this solution is giving me RE.
Only first case is giving RE
def ma(i,j):
l[i][j]=β€˜0’
g=1
if i-1>=0 and l[i-1][j]==β€˜1’:
g+=ma(i-1,j)
if i+1<n and l[i+1][j]==β€˜1’:
g+=ma(i+1,j)
if j-1>=0 and l[i][j-1]==β€˜1’:
g+=ma(i,j-1)
if j+1<m and l[i][j+1]==β€˜1’:
g+=ma(i,j+1)
return g

for _ in range(int(input())):
n,m=map(int,input().split())
l=[]
for i in range(n):
l.append(list(input().strip()))
x=[];y=1
for i in range(n):
for j in range(m):
if l[i][j]==β€˜1’:
x.append(ma(i,j))
x.sort(reverse=True)
e=0
for i in range(len(x)):
if i%2!=0:
e+=x[i]
print(e)

You have to use a Visited Matrix that keeps track of visited cells. Otherwise, your function keeps calling itself causing β€œRecursion limit reached” - Runtime error.

1 Like

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

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;
}
}

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

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;

}

My BFS solution

why my bfs solution is giving TLE?

where as my dfs solution is getting accepted
My DFS solution

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

Thank you so much for the help

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

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

oh thank you very much

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;
        }
}

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)

Time Complexity:

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

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;

}