FENCE - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Ashish Gupta
Tester: Zhong Ziqian
Editorialist: Oleksandr Kulkov

DIFFICULTY:
SIMPLE
PREREQUISITES:
Basic data structures
PROBLEM:
You’re given N\times M grid, K cells in this grid contain a plant. You’re going to build a fence between each pair of adjacent cells u and v such that exactly one of these cells contains plant. Also fence must be built on the boundary of the grid if adjacent cell to this boundary contains plant.
EXPLANATION:
Let’s keep a two-dimensional map in which for cell (x,y) we will keep 1 if it contains plant and 0 otherwise. When you add a new plant (x,y) you have to check all the adjacent cells:

\{(x+1,y),(x,y+1),(x-1,y),(x,y-1)\}

For each cell which doesn’t contain a plant you have to add 1 to the answer and for each cell which contains a plant you should subtract 1. In first case you have to create a fence to separate our cell from that neighbor and in the second case you have to remove the fence because both adjacent cells are plants now. Possible implementation:

int N, M, K;
cin >> N >> M >> K;
map<int, map<int, int>> A;
int ans = 0;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
while(K--) {
	int x, y;
	cin >> x >> y;
	for(int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		ans += A[nx][ny] ? -1 : 1;
	}
	A[x][y] = 1;
}
cout << ans << endl;

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

4 Likes

Thank you. That explanation helped. Gave a new logic.

Can you please explain the values of dx and dy arrays

1 Like

@anu788
Here dx and dy is used for checking wether a plant is present in the nearby spots.
In particular dx : It is used here for checking if plant is present above or below the spot(x,y).
like wise dy : It is used here for checking if plant is present to the left of the spot or right.
hope it helps
happy coding …

2 Likes

I did this with map but got partial Correct(70 point) and Wrong answer for the 30 point.
Here is the code.

Anyone check this!!

Can anyone help me to solve this problem I am facing??

Before you solve my query please know that I was not solving the complete question, I was only solving subtask 1 for 30 points.

I get runtime error (SIGSEV) when i submit this code. I think it is because of when I access array values out of valid range. The code runs fine on my machine but rightfully gives error on codechef. Do you have any elegant solution to avoid this problem?
Just because of some invalid corner values I am getting a futile error, I don’t want to write some if conditional statements to solve this problem. It will then get too messy. Please help me!!!

#include<bits/stdc++.h>

using namespace std;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n,m,k;
        cin >> n >> m >> k;
        int arr[n+1][m+1];
        int x[k] = {0};
        int y[k] = {0};
        memset(arr, 0, sizeof arr);
        for(int i=0; i<k; i++){
            int a,b;
            cin >> a >> b;
            x[i] = a;
            y[i] = b;
            arr[a][b] = 1;
        }
        /*for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                cout << arr[i][j] << " ";
            }
            cout << endl;
        }*/
        long long int ans = 0;
        for(int i=0; i<k; i++){
            for(int j = 0; j < 4; j++) {
                int nx = x[i] + dx[j];
                int ny = y[i] + dy[j];
                if(arr[nx][ny] != 1){
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
}

What was the error in your code?

I still am not aware why It gave wrong answer on subtask 1.

I am getting TLE in the first subtask and AC in the second. VERY WEIRD.

@melfice https://www.codechef.com/viewsolution/32557512

Please help… I did exactly what was said in the tutorial…

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int main(){
	BOOST();
	test(t){
		long long n,m,k;cin>>n>>m>>k;
		vector<pair<long long ,long long > > plants;
		map<pair<long long ,long long >,bool>hash1; // true if contsins plants else false
		ll total=0;
		for(long long i=0;i<k;i++){
			long long r,c;
			cin>>r>>c;
			plants.push_back(make_pair(r,c));
			if(r==1 || r==n)total++; // boundry case
			if(c==1 || c==m)total++; // boundry case
			hash1[{r,c}]=true;// true if contains plants
		}
		for(long long i=0;i<k;i++){
			long long r=plants[i].ff,c=plants[i].ss;
			for(long long j=0;j<4;j++){
				long long x=r+dx[j];
				long long y=c+dy[j];
				if(x<1 || x>n || y<1 || y>m )continue; // boundry case already considered
				if(!hash1[{x,y}])total++;
			}
		}
		cout<<total<<endl;
	}
}

you may think of them are direction unit vectors. take an pair of corresponding (dx,dy), you will get unit vectors in (+x axis, -x axis, +y axis, -y axis)

#include

#include<unordered_map>

using namespace std;

//to hash any given pair

struct hash_pair {

template <class T1, class T2>

size_t operator()(const pair<T1, T2>& p) const{

  auto hash1 = hash<T1>{}(p.first);

  auto hash2 = hash<T2>{}(p.second);

  return hash1 ^ hash2;

}

};

int main()

{

int t;

cin>>t;

int dx[]={1,0,-1,0};

int dy[]={0,1,0,-1};

while(t--)

{

    int n,m,k;

    cin>>n>>m>>k;

    unordered_map<pair<int,int>,int,hash_pair> mp;

    pair<int,int> a[k];

    for(int i=0;i<k;i++)

    {

        int x,y;

        cin>>x>>y;

        mp[{x,y}]++;

        a[i]={x,y};

    }

    long long ans=0;

    for(int i=0;i<k;i++)

    {

        for(int j=0;j<4;j++)

        {

            //cout<<a[i].first+dx[j]<<" "<<a[i].second+dy[j]<<" ";

            if(mp.find({a[i].first+dx[j],a[i].second+dy[j]})==mp.end())

            {

                //cout<<a[i].first+dx[j]<<" "<<a[i].second+dy[j];

                ans++;

            }

        }

    }

    cout<<ans<<"\n";

}

}

Why am i getting TLE in first and third test case? i don’t get it
Thanks for helping in advance