HackerRank Bike Racers Problem Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

long long *array;
int cmp(const void *a, const void *b){
    long long ia = *(long long *)a;
    long long ib = *(long long *)b;
    return array[ia] < array[ib] ? -1 : array[ia] > array[ib];
}
int isValid(int mbikes, int nmen, int k, int z, long long index[]);

int main() {
    //find the k shortes edges "in the bipartite graph" between men & bikes
    //performance metric is the max distance among the k pairs
    //this is a min max problem, minimizing the max distance
    int nmen,mbikes,kspots;
    scanf("%d %d %d",&nmen,&mbikes,&kspots);
    long men[nmen][2], bikes[mbikes][2];
    for(int i=0;i<nmen;i++){scanf("%ld %ld",&men[i][0],&men[i][1]);}
    for(int i=0;i<mbikes;i++){scanf("%ld %ld",&bikes[i][0],&bikes[i][1]);}
    long long d,dists[mbikes*nmen];
    for(int i=0;i<mbikes;i++){
        for(int j=0;j<nmen;j++){
            d=(bikes[i][0]-men[j][0]);
            dists[i*nmen+j]=d*d;
            d=(bikes[i][1]-men[j][1]);
            dists[i*nmen+j]+=d*d;          
        }
    }
    //sort distances, only really need k smallest from each bike
    //discard those that are larger (but not those that are equal)
    long long index[mbikes*nmen];//use malloc to large size array
    for(long i=0;i<mbikes*nmen;i++){index[i] = i;}
    array = dists;
    qsort(index, mbikes*nmen, sizeof(*index), cmp);
    //for(long i=0;i<mbikes*nmen;i++){printf("%lld ",dists[index[i]]);} printf("\n");
    
    int last=kspots;   
    //do binary search to find out minimum dist that allows a valid assignment
    int left=0, right=mbikes*nmen, width=mbikes*nmen, mid;
    while(width>4){
        width/=2; mid=(left+right)/2; 
        //printf("Check %d\n",mid);
        if(!isValid(mbikes,nmen,kspots,mid,index)){ left=mid; }
        else{right=mid;}
    }
    last=right;
    for (int j=left;j<right;j++){
        //printf("Check %d\n",j);
        if(isValid(mbikes,nmen,kspots,j,index)) {last=j;break;}
    } 
    printf("%lld",dists[index[last-1]]);
    return 0;
}

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 1000
#define oo 1000000000
int n;  // number of nodes
int e;  // number of edges
int capacity[MAX_NODES][MAX_NODES]; // capacity matrix
int flow[MAX_NODES][MAX_NODES];     // flow matrix
int color[MAX_NODES]; // needed for breadth-first search               
int pred[MAX_NODES];  // array to store augmenting path
int max_flow (int source, int sink);
int isValid(int mbikes, int nmen, int k, int z, long long index[]){
    //check if we can pick k unique row/col pairs among the first z
    //this is a matching of cardinality k in the bipartite ii-jj graph
    if(z<k) return 0;
    //capacity rows 0-249, cols 250-499, source as 500, sink as 501
    for(int i=0;i<500;i++){
        for(int j=0;j<500;j++){capacity[i][j]=0;}
    }   
    for(int i=0;i<250;i++){capacity[500][i]=1;}
    for(int i=0;i<250;i++){capacity[250+i][501]=1;}
    for(int i=0;i<z;i++){
        int ii=index[i]/nmen;
        int jj=index[i]%nmen;
        capacity[ii][250+jj]=1;
    }
    n=502; e=z+2; 
    int maxflow=max_flow(500,501);
    //printf("Max flow for z= %d\n",maxflow);
    if(maxflow>=k) return 1;
    else return 0;
}
// below follows Ford-Fulkerson algorithm for max matching via max flow

int min (int x, int y) {
    return x<y ? x : y;  // returns minimum of x and y
}
int head,tail;
int q[MAX_NODES+2];
void enqueue(int x){q[tail] = x; tail++; color[x] = GRAY;}
int dequeue(){int x = q[head]; head++; color[x] = BLACK; return x;}
int bfs (int start, int target) {
    int u,v;
    for (u=0; u<n; u++) { color[u] = WHITE; }   
    head = tail = 0;
    enqueue(start);
    pred[start] = -1;
    while (head!=tail) {
        u = dequeue();
        // Search all adjacent white nodes v. If the capacity
        // from u to v in the residual network is positive, enqueue v.
        for (v=0; v<n; v++) {
            if (color[v]==WHITE && capacity[u][v]-flow[u][v]>0) {
                enqueue(v); pred[v] = u;
            }
        }
    }
    // If the color of the target node is black now, it means that we reached it.
    return color[target]==BLACK;
}
int max_flow (int source, int sink) {
    int i,j,u;
    // Initialize empty flow.
    int max_flow = 0;
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            flow[i][j] = 0;
        }
    }
    // While there exists an augmenting path, increment the flow along this path.
    while (bfs(source,sink)) {
        // Determine the amount by which we can increment the flow.
        int increment = oo;
        for (u=n-1; pred[u]>=0; u=pred[u]) {
            increment = min(increment,capacity[pred[u]][u]-flow[pred[u]][u]);
        }
        // Now increment the flow.
        for (u=n-1; pred[u]>=0; u=pred[u]) {
            flow[pred[u]][u] += increment; flow[u][pred[u]] -= increment;
        }
        max_flow += increment;
    }
    // No augmenting path anymore. We are done.
    return max_flow;
}
                    

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

#define maxN 1000000007
#define PI 3.14159265358979
#define bb __builtin_popcount
#define ll long long
const int N = 505;
long long n, m, Assigned[N], kkk;
long long Visited[N], t=0;
vector<int> a[N];
long long dx[N], dy[N], cx[N], cy[N];
bool visit(int u) {
    if (Visited[u]!=t)
        Visited[u]=t;
    else
        return false;

    for (int i=0; int v=a[u][i]; i++)
    if (!Assigned[v] || visit(Assigned[v])) {
        Assigned[v]=u;
        return true;
    }
    return false;
}
long long xet(int i, int j) {
    return (long long) (cx[i] - dx[j]) * (cx[i] - dx[j]) + (cy[i] - dy[j]) * (cy[i] - dy[j]);
}
bool duyet(long long mid) {
    for (int i = 1; i <= m + n; i++) {
        a[i].clear();
        Assigned[i] = 0;
        Visited[i] = 0;
    }
    //cout << "INIT: " << endl;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (xet(i, j) <= mid)  a[i].push_back(j + n);
    //cout << "INIT END: " << endl;
    for (int i = 1; i <= n; i++) a[i].push_back(0);
    int Count = 0;
    for (int i = 1; i <= n; i++) {
        t++;
        Count += visit(i);
    }
    //cout << mid << " " << Count << endl;
    if (Count >= kkk) return true;
    return false;
}
void solve() {
    cin >> n >> m >> kkk;
    for (int i = 1; i <= n; i++) cin >> cx[i] >> cy[i];
    for (int i = 1; i <= m; i++) cin >> dx[i] >> dy[i];
    long long l = 0, r = 1000000000000000000;
    while (l < r) {
        long long mid = (l + r) / 2;
        if (duyet(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    //freopen("main.in", "r", stdin);
    //freopen("main.in", "w", stdout);
    //freopen("main.out", "w", stdout);
    solve();
    //fclose(stdin);
    //fclose(stdout);
}

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    using System.IO;

    namespace Hackerrank
    {
        class Program
        {
            static void Main(string[] args)
            {

                Problem problem = new Problem();
                problem.run();
            }
        }

        public class Problem
        {
            private int numberCandidates, numberBikes, neededBikers;
            private Point[] bikes;
            private Point[] candidates;
            private long[,] bikerBikesDistances;

            public void run()
            {
                getInput();

                Console.WriteLine(GetMinTime());

                Console.ReadKey();
            }
            
            private void getInput()
            {
                string[] line = Console.ReadLine().Split(' ');
                numberCandidates = Convert.ToInt32(line[0]);
                numberBikes = Convert.ToInt32(line[1]);
                neededBikers = Convert.ToInt32(line[2]);
                candidates = new Point[numberCandidates];
                bikes = new Point[numberBikes];

                for (int i = 0; i < numberCandidates; i++)
                {
                    candidates[i] = ReadCoordinates();
                }

                for (int i = 0; i < numberBikes; i++)
                {
                    bikes[i] = ReadCoordinates();
                }

                SetBikerBikeDistances();
            }

            private Point ReadCoordinates()
            {
                string[] line = Console.ReadLine().Split(' ');
                int x = Convert.ToInt32(line[0]);
                int y = Convert.ToInt32(line[1]);

                return new Point(x, y);
            }

            private void SetBikerBikeDistances()
            {
                bikerBikesDistances = new long[numberCandidates, numberBikes];

                for(int i = 0; i < numberCandidates; i++){
                    for(int j = 0; j < numberBikes; j++){
                        bikerBikesDistances[i, j] = GetTimeSquare(candidates[i], bikes[j]);
                    }
                }
            }

            private long GetTimeSquare(Point a, Point b)
            {
                return (long)(Math.Pow(a.X - b.X, 2) + Math.Pow(a.Y - b.Y, 2));
            }

            private long GetMinTime()
            {
                long bottom = 0;
                long top = (long)Math.Pow(10, 16);
                while (bottom < top)
                {
                    long middle = (top + bottom) / 2;
                    if (CanAccomodateBikersInGivenTime(middle))
                    {
                        top = middle;
                    }
                    else
                    {
                        bottom = middle + 1;
                    }
                }

                return top;
            }

            private bool CanAccomodateBikersInGivenTime(long middle)
            {
                return MaximumBipartiteMatching(BuildBipartiteGraph(middle)) >= neededBikers;
            }

            private bool[,] BuildBipartiteGraph(long timeLimit)
            {
                bool[,] timeGraph = new bool[numberCandidates, numberBikes];
                for (int i = 0; i < numberCandidates; i++)
                {
                    for (int j = 0; j < numberBikes; j++)
                    {
                        if (bikerBikesDistances[i, j] <= timeLimit)
                        {
                            timeGraph[i, j] = true;
                        }
                        else
                        {
                            timeGraph[i, j] = false;
                        }
                    }
                }

                return timeGraph;
            }

            private int MaximumBipartiteMatching(bool[,] graph)
            {
                int bikersAccomodated = 0;
                //when bike is assinged we set the index of the biker from the bikers array in its cell
                int[] matchBikersWithBikes = new int[numberBikes];
                //initialize the match array, -1 represents a bike that is still available
                SetArrayToSingleValue(matchBikersWithBikes, -1);

                for (int i = 0; i < numberCandidates; i++)
                {
                    bool[] bikesTaken = new bool[numberBikes];
                    SetArrayToSingleValue(bikesTaken, false);
                    // Find if the candidate can get a bike
                    if (CanBikerGetABike(graph, i, bikesTaken, matchBikersWithBikes))
                    {
                        bikersAccomodated++;
                    }
                }

                return bikersAccomodated;
            }

            private bool CanBikerGetABike(bool[,] graph, int bikerIndex, bool[] bikesTaken, int[] matchBikersWithBikes)
            {
                for (int i = 0; i < numberBikes; i++)
                {
                    if (graph[bikerIndex, i] && !bikesTaken[i])
                    {
                        bikesTaken[i] = true;
                        //if bike i is not already taken OR the biker that took it can find another bike, assign bike to biker and return true.
                        //since the bike is marked as taken in bikesTaken, the recursive search for substitute bike will not offer that bike
                        if (matchBikersWithBikes[i] < 0 || CanBikerGetABike(graph, matchBikersWithBikes[i], bikesTaken, matchBikersWithBikes))
                        {
                            matchBikersWithBikes[i] = bikerIndex;

                            return true;
                        }
                    }
                }

                return false;
            }

            private void SetArrayToSingleValue<T>(T[] array, T value)
            {
                for (int i = 0; i < array.Count(); i++)
                {
                    array[i] = value;
                }
            }
        }

        public class Point
        {
            public int X { get; set; }
            public int Y { get; set; }

            public Point() { }

            public Point(int x, int y)
            {
                this.X = x;
                this.Y = y;
            }
        }

    }

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class Solution {
    static BufferedReader in = new BufferedReader(new InputStreamReader(
            System.in));
    static StringBuilder out = new StringBuilder();

    private static Node source;
    private static Node sink;
    private static Node[] bikers;
    private static Node[] bikes;
    
    
    public static void main(String[] args) throws IOException {
        String line = in.readLine();
        String[] data = line.split("\\s+");
        int numBikers = Integer.parseInt(data[0]);
        int numBikes = Integer.parseInt(data[1]);
        int numRequired = Integer.parseInt(data[2]);

        source = new Node();
        sink = new Node(true);
        bikers = new Node[numBikers];
        bikes = new Node[numBikes];
        
        Coordinate[] bikerPos = new Coordinate[numBikers];
        
        for(int i = 0; i < numBikers; i ++)
        {
            bikers[i] = new Node();
            source.addConnection(bikers[i]);
            line = in.readLine();
            data = line.split("\\s+");
            bikerPos[i] = new Coordinate(Integer.parseInt(data[0]), Integer.parseInt(data[1]));
        }
        
        ArrayList<BikerBikeDistance> bbd = new ArrayList<>();
        
        for(int j = 0; j < numBikes; j ++)
        {
            bikes[j] = new Node();
            bikes[j].addConnection(sink);
            line = in.readLine();
            data = line.split("\\s+");
            int bx = Integer.parseInt(data[0]);
            int by = Integer.parseInt(data[1]);
            for(int i = 0; i < numBikers; i ++)
            {
                bbd.add(new BikerBikeDistance(i, j, getCost(bx, by, bikerPos[i].x, bikerPos[i].y)));
            }
        }
        
        Collections.sort(bbd);
        
        
        int total = 0;
        long dist = 0;
        for(int i = 0; total < numRequired; i ++)
        {
            BikerBikeDistance cbbd = bbd.get(i);
            dist = cbbd.cost;
            bikers[cbbd.biker].addConnection(bikes[cbbd.bike]);
            if(source.dfsAndReverse(i))
            {
                total ++;
            }
        }
        System.out.println(dist);
    }
    
    
    private static long getCost(long x1, long y1, long x2, long y2)
    {
        return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    }
    
    private static class Coordinate
    {
        final int x;
        final int y;
        
        public Coordinate(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    
    private static class BikerBikeDistance implements Comparable<BikerBikeDistance>
    {
        final int biker;
        final int bike;
        final long cost;
        String name;
        
        public BikerBikeDistance(int biker, int bike, long cost)
        {
            this.biker = biker;
            this.bike = bike;
            this.cost = cost;
        }

        @Override
        public int compareTo(BikerBikeDistance o) {
            if(cost < o.cost)
            {
                return -1;
            }
            if(cost > o.cost)
            {
                return 1;
            }
            return 0;
        }
    }
    
    private static class Node
    {
        private LinkedList<Node> connections;
        private int visitedNum;
        private boolean isTerminus;
        
        public Node()
        {
            connections = new LinkedList<Node>();
            visitedNum = -999;
            isTerminus = false;
        }
        
        public Node(boolean terminus)
        {
            connections = new LinkedList<Node>();
            visitedNum = -999;
            isTerminus = terminus;
        }
        
        public int getVisited()
        {
            return visitedNum;
        }
        
        public void addConnection(Node n)
        {
            connections.add(n);
        }
        
        public boolean dfsAndReverse(int v)
        {
            if(isTerminus)
            {
                return true;
            }
            visitedNum = v;
            Iterator<Node> i = connections.iterator();
            while(i.hasNext())
            {
                Node n = i.next();
                if(n.getVisited()!=v)
                {
                    if(n.dfsAndReverse(v))
                    {
                        n.addConnection(this);
                        i.remove();
                        return true;
                    }
                }
            }
            return false;
        }
    }
}

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the bikeRacers function below.
 */
function bikeRacers(bikers, bikes, K) {

    function maxBipartiteMatch(matrix, isConnected) {
        function hasMatch(u) {
            for (var v = 0; v < M; v++) {
                if (isConnected(matrix[u][v]) && !visited[v]) {
                    visited[v] = 1;

                    if (matches[v] === -1 || hasMatch(matches[v])) {
                        matches[v] = u;
                        return true;
                    }
                }
            }
            return false;
        }
        var N = matrix.length;
        var M = matrix[0].length;
        var visited = new Array(M);
        var matches = new Array(M);
        var res = 0;
        isConnected = isConnected || function (x) { return x };
        for (var i = 0; i < M; i++) {
            matches[i] = -1;
        }
        for (var u = 0; u < N; u++) {
            for (var k = 0; k < M; k++) {
                visited[k] = 0;
            }
            if (hasMatch(u)) {
                res++;
            }
        }
        return res;
    }

    var origMatrix = [];
    var workMatrix = [];
    var sortArr = [];

    for (var i = 0; i < bikers.length; i++) {
        origMatrix[i] = [];
        workMatrix[i] = [];
        for (var j = 0; j < bikes.length; j++) {
            var v = Math.pow(Math.abs(bikers[i][0] - bikes[j][0]), 2) + Math.pow(Math.abs(bikers[i][1] - bikes[j][1]), 2)
            origMatrix[i][j] = v;
            workMatrix[i][j] = v;
            sortArr.push(v);
        }
    }
    sortArr.sort((a, b) => a - b);
    var left = 0;
    var mid = 0;
    var right = sortArr.length - 1;
    var ans = sortArr[right];
    while (left <= right) {
        mid = left + Math.ceil((right - left) / 2);
        for (var i = 0; i < bikers.length; i++) {
            for (var j = 0; j < bikes.length; j++) {
                if (origMatrix[i][j] <= sortArr[mid]) {
                    workMatrix[i][j] = 0;
                } else {
                    workMatrix[i][j] = origMatrix[i][j];
                }
            }
        }
        var matchN = maxBipartiteMatch(workMatrix, (x) => !x);
        if (matchN < K) {
            left = mid + 1;
        } else {
            right = mid - 1;
            ans = Math.min(ans, sortArr[mid]);
        }
    }
    return ans;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nmk = readLine().split(' ');

    const n = parseInt(nmk[0], 10);

    const m = parseInt(nmk[1], 10);

    const k = parseInt(nmk[2], 10);

    let bikers = Array(n);

    for (let bikersRowItr = 0; bikersRowItr < n; bikersRowItr++) {
        bikers[bikersRowItr] = readLine().split(' ').map(bikersTemp => parseInt(bikersTemp, 10));
    }

    let bikes = Array(m);

    for (let bikesRowItr = 0; bikesRowItr < m; bikesRowItr++) {
        bikes[bikesRowItr] = readLine().split(' ').map(bikesTemp => parseInt(bikesTemp, 10));
    }

    let result = bikeRacers(bikers, bikes, k);

    ws.write(result + "\n");

    ws.end();
}

#!/bin/python3

from collections import deque

debug = False

def show(matrix):
  if False:
    for row in matrix:
      print(str(row))

def cost(r,b):
  dx = b[0]-r[0]
  dy = b[1]-r[1]
  return dx*dx+dy*dy

def check(limit): # can we connect k riders to k bicycles with only segments less than limit?
  rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
  btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
  # assign as many as we can, stop if we can get to k of them
  assd_r = {}
  assd_b = {}
  assd = 0
  arb = False
  assdnow = True
  while assdnow:
    if debug:
      print("Looping through")
    assdnow = False
    for r in range(n):
      if r not in assd_r:
        # node isn't assigned yet; try and find an augmenting path (DFS)
        # leads from this r to any unassigned b, possibly going through current assignations
        paths = deque() # contains candidate augmenting paths
        visited_r = set()
        visited_r.add(r)
        for b in reversed(rtob[r]):
          paths.append([(r,b)])
        while paths:
          path = paths.pop()
          rc, b = path[-1] # last tuple, try and expand from here
          # candidate: rc -> b
          if b not in assd_b:
            # b isn't assigned; this is an augmenting path
            if debug:
              print("assigning", path)
            for rc, b in path:
              assd_r[rc] = b
              assd_b[b] = rc
            assd += 1
            if assd >= k:
              if debug:
                print("Success! Assigned %d nodes of %d"%(assd,k))
              return True
            assdnow = True
            break # augmenting path found
          else: # b is assigned; follow the assigment back to an r (but not the same one) and try again
            if debug:
              print("continuing", path)
            rc = assd_b[b]
            if rc not in visited_r:
              visited_r.add(rc)
              for bc in reversed(rtob[rc]):
                if b != bc:
                  np = path[:]
                  np.append((rc,bc))
                  paths.append(np)
  if debug:
    print("Failure! Assigned %d nodes of %d"%(assd,k))
  return False

n,m,k = map(int,input().split())
rs = [tuple(map(int,input().split())) for _ in range(n)] # riders
bs = [tuple(map(int,input().split())) for _ in range(m)] # bicycles
c = [[cost(r,b) for b in bs] for r in rs] # adjacency graph - dense
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
# binary search using check function
lo = 0
hi = len(segs) - 1
while lo < hi:
  # invariant: smallest to succeed is x | lo <= x <= hi
  mid = (hi + lo) // 2
  if debug:
    print("examining (%d,%d,%d) (%d)"%(lo,mid,hi,segs[mid]))
  if check(segs[mid]):
    # succeeded, make mid highest in range (keep it since it might be target)
    hi = mid
  else:
    # failed, try more edges (mid can't be target)
    lo = mid + 1
# lo <- smallest to succeed
print(segs[lo])