fence - codechef april 2019 long challenge

Question

In the following question I am getting only 2 correct answers for the code given below. Please help me with what cases are going wrong.

https://www.codechef.com/problems/FENCE

The idea is to account for every fence encountered when we travel row and column wise.

Once a plant is encountered 2 edges are counted (in both row-wise and column-wise traversal), the previous is checked for adjacency in the row or column. If adjacent, the 2 common edges are subtracted.

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

typedef long long int ll;

bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b) 
    { 
    return (a.second < b.second); 
    } 

int main() {

    ll t;
    cin>>t;
    while(t--){
        ll n,m,k;
        cin>>n>>m>>k;
        vector<pair<ll,ll>> a(k,make_pair(0,0));
        ll count=4;
        if(k==0) count=0;
        else{
            ll x,y;
            int l=1;
            cin>>x>>y;
            a[0]=make_pair(x,y);

            for(ll i=1;i<k;i++){
            ll x,y;
            cin>>x>>y;
            a[l]=make_pair(x,y);
            if(a[l]!=a[l-1]) l++;
            }

            sort(a.begin(),a.end());

            for(ll i=1;i<k;i++){

            if((a[i-1].first==a[i].first && a[i-1].second+1==a[i].second)) count-=2;
            count+=2;
            }

            sort(a.begin(),a.end(),sortbysec);

            for(ll i=1;i<k;i++){

            if((a[i-1].second==a[i].second && a[i-1].first+1==a[i].first)) count-=2;
            count+=2;
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

What have you done to narrow it down? What is the data set that is failing? What is the expected result for that data set? — Retired Ninja, May 21 '19 at 11:31
Also, what method do you use to solve the problem ? It can be helpful for external readers to have a summary of your code rather than to have to read and understand it. — m.raynal, May 21 '19 at 11:45
What do you use `sort` for ? It seems strange to see a call to a sorting function to solve this problem. — m.raynal, May 21 '19 at 11:47
`if(k==0) count=0;` is already wrong: the problem statement says that it is impossible to leave the field without crossing the fence. — user58697, May 21 '19 at 16:10
(OT: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)) — Biffen, May 22 '19 at 10:22

maraca · Answer 1 · 2019-05-22T10:16:56.980

You cannot write an algorithm where you construct the grid, this has at least complexity of O(MN) and as you can see in the constraints NM <= 10^18 which is not feasible.

You have to write an algorithm with complexity O(K), because we know the number of plants K <= 10^5.

It can be done pretty easily:

Create a HashMap<Integer, HashSet<Integer>> where you put in all the plant values. The goal is to query adjacent cells in O(1).
Then for each plant you add 4 - adjacent plants to the fence sum. E.g. if you want to test if {3, 7000} has a plant to the left, you do map.containsKey(2) && map.get(2).contains(7000). Like this you don't even need special treatment of plants at the border of the grid.

fence - codechef april 2019 long challenge

1 Answers1