HackerEarth Telecom Towers problem solution

In this HackerEarth Telecom Towers problem solution Telecom towers are an integral part of the telecom network infrastructure. In fact they are the most expensive to build and the valuations are heavy. The newly started mobile company in Hacker Land built n towers to enhance the connectivity of their users. You can assume that the Cartesian coordinate system is used in Hacker Land and the location of ith tower is given as (xi,yi).  

After the construction of the towers company realised that there are many call drops happening with the users. One identified reason for the frequent call drop was that the pair of towers which are at Euclidean distance  were causing destructive interference. To resolve the issue the company decided to destroy some towers such that no two towers are at   distance. You have to tell the minimum number of towers that the company need to destroy such that no two towers are at distance d.

HackerEarth Telecom Towers problem solution.

#include "bits/stdc++.h"
using namespace std;
struct ${$(){ios_base::sync_with_stdio(0);cin.tie(0);}}$;

const int inf = 1000111;
struct Matching {
    int n;
    vector<int> matchL, matchR, dist;
    vector<bool> seen;
    vector< vector<int> > ke;

    Matching(int n) : n(n), matchL(n+1), matchR(n+1), dist(n+1), seen(n+1, false), ke(n+1) {}

    void addEdge(int u, int v) {
        ke[u].push_back(v);
    }

    bool bfs() {
        queue<int> qu;
        for(int u = 1; u <= n; ++u)
            if (!matchL[u]) {
                dist[u] = 0;
                qu.push(u);
            } else dist[u] = inf;
        dist[0] = inf;

        while (!qu.empty()) {
            int u = qu.front(); qu.pop();
            for(__typeof(ke[u].begin()) v = ke[u].begin(); v != ke[u].end(); ++v) {
                if (dist[matchR[*v]] == inf) {
                    dist[matchR[*v]] = dist[u] + 1;
                    qu.push(matchR[*v]);
                }
            }
        }
        return dist[0] != inf;
    }

    bool dfs(int u) {
        if (u) {
            for(__typeof(ke[u].begin()) v = ke[u].begin(); v != ke[u].end(); ++v)
                if (dist[matchR[*v]] == dist[u] + 1 && dfs(matchR[*v])) {
                    matchL[u] = *v;
                    matchR[*v] = u;
                    return true;
                }
            dist[u] = inf;
            return false;
        }
        return true;
    }

    int match() {
        int res = 0;
        while (bfs()) {
            for(int u = 1; u <= n; ++u)
                if (!matchL[u])
                    if (dfs(u)) ++res;
        }
        return res;
    }
};



const int N = 205;
int x[N * N], y[N * N];
int color[N * N];


bool good(int i, int j) {
   return i >= 0 && i < N && j >= 0 && j < N;
}

vector <int> adj[N * N];

void add_edge(int i, int j, int i_, int j_) {
  // DEBUG(N);
   int u = i * N + j;
   int v = i_ * N + j_;
   // DEBUG(i, j, i_, j_);
   adj[u].push_back(v);
   adj[v].push_back(u);
}

int m[N][N];
int main() {
   int n, d;
   cin >> n >> d;


   map <pair<int, int>, int> rmap;
   for(int i = 1; i <= n; i++) {
      cin >> x[i] >> y[i];
      rmap[{x[i], y[i]}] = i;
   }

   vector <pair <int, int> > side;

   for(int a = -d; a <= d; a++) {
      for(int b = -d; b <= d; b++) {
         if(a * a + b * b == d * d) {
            side.push_back({a, b});
         }
      }
   }


    int edge = 0;
    for(int i = 0; i < N; i++){
       for(int j = 0; j < N; j++){
          for(auto t: side) {
             int i_ = i + t.first;
             int j_ = j + t.second;
             if(good(i_, j_)) {
                add_edge(i, j, i_, j_);
                edge++;
             }
          }
       }
    }


    memset(color, -1, sizeof color);

    bool is_bipartite = true;
    queue <int> q;

    for(int st = 0; st < N * N; st++) {
       if(color[st] == -1) {
          q.push(st);
          color[st] = 0;
          while(!q.empty()) {
             int v = q.front();
             q.pop();
             for(auto u: adj[v]) {
                if(color[u] == -1) {
                   color[u] = color[v] ^ 1;
                   q.push(u);
                } else {
                   // is_bipartite = false;
                   is_bipartite &= color[u] != color[v];
                }
             }
          }
       }
    }

    int cnt[2];
    cnt[0] = cnt[1] = 1;

    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        m[i][j] = cnt[color[i * N + j]];
        cnt[color[i * N + j]]++; 
      }
    }

    assert(is_bipartite);

   Matching M(N * N);

   for(int i = 1; i <= n; i++) {
      for(auto ab: side) {
         int a = x[i] + ab.first;
         int b = y[i] + ab.second;
         if(rmap.find({a, b}) != rmap.end()) {
            if(color[x[i] * N + y[i]] == 0) {
              assert(color[a * N + b] == 1);
              M.addEdge(m[x[i]][y[i]], m[a][b]);
            }
         }
      }
   }

   cout << M.match() << endl;
   return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 10007;
const int INF = 1000000000;

vector <int> G[MAXN];
map <pii,int> M;
int col[MAXN];

struct max_flow
{
  // from e-maxx.ru/algo
  struct edge {
    int a, b, cap, flow;
  };

  int n, s, t, d[MAXN], ptr[MAXN], q[MAXN]; //n, s, t must be set prior to calling dinics
  vector<edge> e;
  vector<int> g[MAXN];

  void add_edge (int a, int b, int cap) {
    edge e1 = { a, b, cap, 0 };
    edge e2 = { b, a, 0, 0 };
    g[a].push_back ((int) e.size());
    e.push_back (e1);
    g[b].push_back ((int) e.size());
    e.push_back (e2);
  }

  bool bfs() {
    int qh=0, qt=0;
    q[qt++] = s;
    memset (d, -1, n * sizeof d[0]);
    d[s] = 0;
    while (qh < qt && d[t] == -1) {
      int v = q[qh++];
      for (size_t i=0; i<g[v].size(); ++i) {
        int id = g[v][i],
          to = e[id].b;
        if (d[to] == -1 && e[id].flow < e[id].cap) {
          q[qt++] = to;
          d[to] = d[v] + 1;
        }
      }
    }
    return d[t] != -1;
  }

  int dfs (int v, int flow) {
    if (!flow)  return 0;
    if (v == t)  return flow;
    for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
      int id = g[v][ptr[v]],
        to = e[id].b;
      if (d[to] != d[v] + 1)  continue;
      int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));
      if (pushed) {
        e[id].flow += pushed;
        e[id^1].flow -= pushed;
        return pushed;
      }
    }
    return 0;
  }

  int dinic() {
    int flow = 0;
    for (;;) {
      if (!bfs())  break;
      memset (ptr, 0, n * sizeof ptr[0]);
      while (int pushed = dfs (s, INF))
        flow += pushed;
    }
    return flow;
  }
};
void dfs(int pos)
{
  for (int i = 0; i < G[pos].size(); ++i)
  {
    if(col[G[pos][i]] == -1)
    {
      col[G[pos][i]] = 1 - col[pos];
      dfs(G[pos][i]);
    }
  }
}
int main(int argc, char const *argv[])
{
  int n,d;
  cin>>n>>d;
  vector <pii> triplets;
  for (int i = -d; i <= d; ++i)
  {
    for (int j = -d; j <= d; ++j)
    {
      if(i*i + j*j == d*d)
      {
        triplets.push_back(pii(i,j));
      }
    }
  }
  for (int i = 0; i < n; ++i)
  {
    int x,y;
    cin>>x>>y;
    M[pii(x, y)] = i;
    for (int j = 0; j < triplets.size(); ++j)
    {
      int nx = x + triplets[j].first, ny = y + triplets[j].second;
      if(M.find(pii(nx,ny)) != M.end())
      {
        int id = M[pii(nx,ny)];
        G[i].push_back(id);
        G[id].push_back(i);
      }
    }
  }
  memset(col, -1, sizeof col);
  for (int i = 0; i < n; ++i)
  {
    if(col[i] == -1)
    {
      col[i] = 0;
      dfs(i);
    }
  }

  max_flow flow_graph;
  
  flow_graph.n = n + 2;
  flow_graph.s = n;
  flow_graph.t = n + 1;

  for (int i = 0; i < n; ++i)
  {
    if(col[i] == 0)
    {
      flow_graph.add_edge(flow_graph.s, i, 1);
      for (int j = 0; j < G[i].size(); ++j)
      {
        flow_graph.add_edge(i, G[i][j], 1);
      }
    }
    else
      flow_graph.add_edge(i, flow_graph.t, 1);
    
  }
  cout<<flow_graph.dinic()<<"\n";
  return 0;
}