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 
?
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;
}
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);
}
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.
Bro try to add recursion limit like
from sys import setrecursionlimit
setrecursionlimit(100000)
it will worked for me
Bro try to add recursion limit like in python
from sys import setrecursionlimit
setrecursionlimit(100000)
it will worked for me
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;
}//
// 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?
from sys import setrecursionlimit
setrecursionlimit(100000)
T = int(input())
def CheckSide1(x,y):
global COUNT
W[x][y] = 0
if x+1<=N-1 and W[x+1][y]==1:
COUNT+=1
CheckSide1(x+1,y)
if y+1<=M-1 and W[x][y+1]==1:
COUNT+=1
CheckSide1(x,y+1)
if x-1>=0 and W[x-1][y]==1:
COUNT+=1
CheckSide1(x-1,y)
if y-1>=0 and W[x][y-1]==1:
COUNT+=1
CheckSide1(x,y-1)
else:
return
for i in range(T):
COUNT=0
W = []
res = []
N,M = input().split()
N,M = [int(N), int(M)]
for k in range(N):
x = [int(x) for x in str(input())]
W.append(x)
for i in range(N):
for j in range(M):
if W[i][j]==1:
COUNT=1
CheckSide1(i,j)
res.append(COUNT)
COUNT=0
res = sorted(res)
points = [0, 0]
for i in range(0, len(res)):
if(i % 2):
points[1] += res[i]
else :
points[0] += res[i]
print(points[1])
Why I’m getting WA, can anyone explain?
@vichitr could you plz tell me why my code is giving WA in last subtask…
or can you give any tc for which code is giving WA
CodeChef: Practical coding for everyone
1 Like
Mistake:
if(x-1<n && grid[x-1][y]=='1')
{
q.push(make_pair(x-1,y));
grid[x-1][y]='0';
}
if(y-1<m && grid[x][y-1]=='1')
{
q.push(make_pair(x,y-1));
grid[x][y-1]='0';
}
The check x-1<n instead of x-1>=0 and y-1<m instead of y-1>=0.
1 Like
ohh yeah, thanks!
I am facing a very weird error in which after the function ends instead of coming back to main and running the next test case it give me a runtime error pls help.
#include <bits/stdc++.h>
using namespace std;
int counter, n, m;
void visit(int i, int j, vector<vector<bool>> &vis, string *dfs)
{
if(vis[i][j]==0)
{
vis[i][j]=1;
if(dfs[i][j]=='0')
return;
else if(dfs[i][j]=='1')
{
if(i<n-1)
visit(i+1, j, vis, dfs);
if(j<m-1)
visit(i, j+1, vis, dfs);
counter++;
return;
}
}
}
void solve (){
int i, g, answer;
cin>>n>>m;
string dfs[n];
int arr[(n*m)/2];
for(i=0;i<n;i++)
{
cin>>dfs[i];
}
vector<vector<bool>> vis(n, vector<bool>(m, 0));
for(i=0;i<n; i++)
{
for(int j=0;j<m; j++)
{
counter=0;
visit(i, j, vis, dfs);
arr[g]=counter;
g++;
}
}
sort(arr, arr+g, greater<int>());
for(i=1;i<g;i=i+2)
{
answer=arr[i]+answer;
}
cout<<answer<<endl;
return;
}
int main() {
int t;
cin>>t;
while (t--){
solve();
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector<string> ans;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
ans.push_back(s);
}
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<vector<int>> vis(n, vector<int>(m, 0));
vector<int> groups;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (ans[i][j] == '1' && vis[i][j] == 0)
{
int count = 0;
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty())
{
auto it = q.front();
q.pop();
count++;
int x = it.first;
int y = it.second;
vis[x][y] = 1;
for (int k = 0; k < 4; k++)
{
int newx = x + dx[k];
int newy = y + dy[k];
if (ans[newx][newy] == '1' && newx<m && newx>=0 && newy<n && newy>=0)
{
q.push({newx, newy});
}
}
}
groups.push_back(count);
}
}
}
sort(groups.begin(),groups.end());
reverse(groups.begin(),groups.end());
}
return 0;
}
bro can u pls tell me why my code is giving tle
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector<string> ans;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
ans.push_back(s);
}
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<vector<int>> vis(n, vector<int>(m, 0));
vector<int> groups;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (ans[i][j] == '1' && vis[i][j] == 0)
{
int count = 0;
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty())
{
auto it = q.front();
q.pop();
count++;
int x = it.first;
int y = it.second;
vis[x][y] = 1;
for (int k = 0; k < 4; k++)
{
int newx = x + dx[k];
int newy = y + dy[k];
if (ans[newx][newy] == '1' && newx<m && newx>=0 && newy<n && newy>=0)
{
q.push({newx, newy});
}
}
}
groups.push_back(count);
}
}
}
sort(groups.begin(),groups.end());
reverse(groups.begin(),groups.end());
int ts=0;
for(int i=0;i<groups.size();i++)
{
if(i%2==1) ts+=groups[i];
}
cout<<ts<<endl;
}
return 0;
}