• Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
Friday, January 27, 2023
  • Login
Zeroplusfour
No Result
View All Result
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
  • Home
  • Top Posts
  • Code Solutions
  • How to
  • News
  • Trending
  • Anime
  • Health
  • Education
No Result
View All Result
Zeroplusfour
No Result
View All Result
Home Code Solutions Hackerrank Algorithms

Ticket – HackerRank Solution

Ticket - HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

bhautik bhalala by bhautik bhalala
May 27, 2022
Reading Time: 1 min read
0
15 Days to learn SQL Hard SQL(Advanced)-Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution alt text

Spread the love

Table of Contents

  • Ticket  – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
  • Solutions of Algorithms Data Structures Hard HackerRank:
    • Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
  • C++ Ticket HackerRank Solution
  • Java Ticket HackerRank Solution
  • C Ticket HackerRank Solution
    • Warmup Implementation Strings Sorting Search Graph Theory Greedy Dynamic Programming Constructive Algorithms Bit Manipulation Recursion Game Theory NP Complete Debugging
    • Leave a comment below
      • Related posts:

Ticket  – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Solutions of Algorithms Data Structures Hard HackerRank:

Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts

C++ Ticket HackerRank Solution


Copy Code Copied Use a different Browser

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <deque>
#include <map>

using namespace std;

#define MAXN 1024*1024
#define x y[cs]
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
#define R(a) ((a)%M)

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> PI;
typedef vector<PI> VPI;
typedef vector<VPI> VVPI;
typedef vector<VVPI> VVVPI;
typedef vector<VVI> VVVI;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<string> VS;

double MinCostMatching(const VVD &cost, VI &Lmate, VI &Rmate) {
  int n = int(cost.size());

  // construct dual feasible solution
  VD u(n);
  VD v(n);
  for (int i = 0; i < n; i++) {
    u[i] = cost[i][0];
    for (int j = 1; j < n; j++) u[i] = min(u[i], cost[i][j]);
  }
  for (int j = 0; j < n; j++) {
    v[j] = cost[0][j] - u[0];
    for (int i = 1; i < n; i++) v[j] = min(v[j], cost[i][j] - u[i]);
  }
  
  // construct primal solution satisfying complementary slackness
  Lmate = VI(n, -1);
  Rmate = VI(n, -1);
  int mated = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (Rmate[j] != -1) continue;
      if (fabs(cost[i][j] - u[i] - v[j]) < 1e-10) {
	Lmate[i] = j;
	Rmate[j] = i;
	mated++;
	break;
      }
    }
  }
  
  VD dist(n);
  VI dad(n);
  VI seen(n);
  
  // repeat until primal solution is feasible
  while (mated < n) {
    
    // find an unmatched left node
    int s = 0;
    while (Lmate[s] != -1) s++;
    
    // initialize Dijkstra
    fill(dad.begin(), dad.end(), -1);
    fill(seen.begin(), seen.end(), 0);
    for (int k = 0; k < n; k++) 
      dist[k] = cost[s][k] - u[s] - v[k];
    
    int j = 0;
    while (true) {
      
      // find closest
      j = -1;
      for (int k = 0; k < n; k++) {
	if (seen[k]) continue;
	if (j == -1 || dist[k] < dist[j]) j = k;
      }
      seen[j] = 1;
      
      // termination condition
      if (Rmate[j] == -1) break;
      
      // relax neighbors
      const int i = Rmate[j];
      for (int k = 0; k < n; k++) {
	if (seen[k]) continue;
	const double new_dist = dist[j] + cost[i][k] - u[i] - v[k];
	if (dist[k] > new_dist) {
	  dist[k] = new_dist;
	  dad[k] = j;
	}
      }
    }
    
    // update dual variables
    for (int k = 0; k < n; k++) {
      if (k == j || !seen[k]) continue;
      const int i = Rmate[k];
      v[k] += dist[k] - dist[j];
      u[i] -= dist[k] - dist[j];
    }
    u[s] += dist[j];
    
    // augment along path
    while (dad[j] >= 0) {
      const int d = dad[j];
      Rmate[j] = Rmate[d];
      Lmate[Rmate[j]] = j;
      j = d;
    }
    Rmate[j] = s;
    Lmate[s] = j;
    
    mated++;
  }
  
  double value = 0;
  for (int i = 0; i < n; i++)
    value += cost[i][Lmate[i]];
  
  return value;
}

int N, M, K;
map<string, double> f;
VI L, R;
VVD cost;
VS d;
double inf = 1e10;

int find ( int n )
{
	if(L[n] < N)
		L[n] = find(L[n]);
	return L[n];
}

int main ()
{
	cin >> N >> M >> K;
	
	d = VS(N);
	cost = VVD(N+M, VD(N+M,0.0));
	
	string _s;
	double _p;
	for (int i = 0; i < K; i += 1)
	{
		cin >> _s >> _p;
		f[_s] = _p;
	}
	
	for (int i = 0; i < N; i += 1)
		cin >> d[i];
	
	for (int i = 0; i < N+M; i += 1)
	{
		for (int j = 0; j < N+M; j += 1)
		{
			if (i >= N)
				cost[i][j] = 0.0;
			else if (j >= N)
				cost[i][j] = f[d[i]];
			else if ( i <= j )
				cost[i][j] = inf;
			else if ( d[i] == d[j] )
				cost[i][j] = 0.8*f[d[i]];
			else
				cost[i][j] = f[d[i]];
		}
	}
	
	cout << MinCostMatching(cost, L, R) << '\n';
	
	for (int i = 0; i < N; i += 1)
		cout << find(i)-N+1 << '\n';
	
	return 0;
}







Java Ticket HackerRank Solution


Copy Code Copied Use a different Browser

/* HackerRank Template */

import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Solution {
	
	static long initTime;
	static final Random rnd = new Random(7777L);
	static boolean writeLog = false;
	
	public static void main(String[] args) throws IOException {
//		initTime = System.currentTimeMillis();
//		try {
//			writeLog = "true".equals(System.getProperty("LOCAL_RUN_7777"));
//		} catch (SecurityException e) {}
//		new Thread(null, new Runnable() {
//			public void run() {
//				try {
//					try {
//						if (new File("input.txt").exists())
//							System.setIn(new FileInputStream("input.txt"));
//					} catch (SecurityException e) {}
//					long prevTime = System.currentTimeMillis();
//					new Solution().run();
//					writeLog("Total time: " + (System.currentTimeMillis() - prevTime) + " ms");
//					writeLog("Memory status: " + memoryStatus());
//				} catch (IOException e) {
//					e.printStackTrace();
//				}
//			}
//		}, "1", 1L << 24).start();
		new Solution().run();
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
		in.close();
	}
	
	/*************************************************************** 
	 * Solution: min-cost-flow on multi-list
	 **************************************************************/

	final int INF = Integer.MAX_VALUE >> 1;
	final Map<String, Integer> indexes = new HashMap<String, Integer>(120);
	final int costOffset = 10000;
	final int edgesCap = 30;
	
	void solve() throws IOException  {
		
		int n = nextInt();
		int m = nextInt();
		int k = nextInt();
		
		int[] prices = new int [k];
		int[] destionations = new int [n];
		
		for (int i = 0; i < k; i++) {
			prices[indexOf(nextToken())] = 5 * nextInt();
		}
		
		for (int i = 0; i < n; i++) {
			destionations[i] = indexOf(nextToken());
		}
		
		
		
		int S = n + n;
		int T = S + 1;
		Net net = new Net(T + 1, n + n * (n - 1) / 2 + n);
		
		for (int i = 0; i < n; i++) {
			net.addDirectedEdge(S, i, 1, 0);
		}
		
		for (int i = 0; i < n; i++) {
			boolean first = true;
			int edges = 0;
			for (int j = i + 1; j < n; j++) {
				int discount = getDiscount(prices, destionations, i, j);
				if (discount == 0) {
					if (++edges <= edgesCap) {
						net.addDirectedEdge(i, n + j, 1, costOffset);
					}
				} else if (first) {
					first = false;
					net.addDirectedEdge(i, n + j, 1, costOffset - discount);
				}
			}
		}
		
		for (int i = 0; i < n; i++) {
			net.addDirectedEdge(n + i, T, 1, 0);
		}
		
		MinCostFlowAlgorithm minCostFlowAlgorithm = new MinCostFlowAlgorithm(net, S, T);
		
		int totalCost = minCostFlowAlgorithm.run(n - m);
		
		for (int i = 0; i < n; i++) {
			totalCost += prices[destionations[i]];
		}
		
		out.println(0.2 * totalCost);
		
		int[] pathIndexes = getPathIndexes(n, net);
		
		for (int pathIndex : pathIndexes) {
			out.println(pathIndex);
		}
	}
	
	int[] getPathIndexes(int n, Net net) {
		int[] pathIndexes = new int [n];
		
		int curIndex = 1;
		
		for (int i = 0; i < n; i++) {
			if (pathIndexes[i] == 0) {
				dfs(net, n, i, curIndex++, pathIndexes);
			}
		}
		
		return pathIndexes;
	}

	void dfs(Net net, int n, int v, int pathIndex, int[] pathIndexes) {
		pathIndexes[v] = pathIndex;
		
		for (int i = net.head[v]; i != 0; i = net.next[i]) {
			NetEdge edge = net.edges[i];
			if (edge.flow == 1) {
				dfs(net, n, edge.to - n, pathIndex, pathIndexes);
			}
		}
		
	}

	int getDiscount(int[] prices, int[] destionations, int i, int j) {
		if (destionations[i] == destionations[j]) {
			return prices[destionations[i]] / 5;
		}
		return 0;
	}

	int indexOf(String key) {
		Integer index = indexes.get(key);
		if (index == null) indexes.put(key, index = indexes.size());
		return index;
	}
	
	class MinCostFlowAlgorithm {
		Net net;
		int[] dist;
		int[] used;
		int[] phi;
		NetEdge[] prev;
		int tick = 1;
		
		int S, T;
		int cost;
		int flow;
		
		MinCostFlowAlgorithm(Net net, int S, int T) {
			this.net = net;
			dist = new int [net.vNum];
			used = new int [net.vNum];
			phi = new int [net.vNum];
			prev = new NetEdge [net.vNum];
			this.S = S;
			this.T = T;
		}
		
		int run(int minFlow) {
			
			cost = flow = 0;
			
			for (;;) {
				
				int pathCost = dijkstra();
				
//				if (pathCost == INF && flow < minFlow) {
//					throw new RuntimeException("Something wrong");
//				}
				
				if (pathCost >= 0 && flow >= minFlow) {
					break;
				}
				
				updateFlow();
			}
			
			return cost - flow * costOffset;
		}
		
		int dijkstra() {
			fill(dist, INF);
			tick++;
			dist[S] = 0;
			
			for (;;) {
				int v = -1;
				for (int i = 0; i < net.vNum; i++)
					if (used[i] != tick && dist[i] != INF && (v == -1 || dist[v] > dist[i]))
						v = i;
				if (v == -1) break;
				used[v] = tick;
				for (int i = net.head[v]; i != 0; i = net.next[i]) {
					NetEdge e = net.edges[i];
					if (e.restCapacity() > 0)
						if (dist[e.to] > dist[v] + e.cost + phi[v] - phi[e.to]) {
							dist[e.to] = dist[v] + e.cost + phi[v] - phi[e.to];
							prev[e.to] = e;
						}
				}
			}
			
			return dist[T];
		}
		
		void updateFlow() {
			for (int v = T; v != S; v = prev[v].from)
				cost += prev[v].inc();
			flow++;
			for (int v = 0; v < net.vNum; v++)
				phi[v] += dist[v] != INF ? dist[v] : dist[T];
		}
		
	}
	
	class NetEdge {
		int from;
		int to;
		int capacity;
		int flow;
		int cost;
		NetEdge back;
		
		NetEdge(int from, int to, int capacity, int cost) {
			this.from = from;
			this.to = to;
			this.capacity = capacity;
			this.cost = cost;
		}
		
		int restCapacity() {
			return capacity - flow;
		}
		
		void connect(NetEdge back) {
			this.back = back;
		}
		
		int inc() {
			flow++;
			back.flow--;
			return cost;
		}
	}
	
	class Net {
		int vNum;
		int[] head;
		int[] next;
		NetEdge[] edges;
		int cnt = 1;
		
		Net(int vNum, int eNum) {
			this.vNum = vNum;
			head = new int [vNum];
			next = new int [2 * eNum + 1];
			edges = new NetEdge [2 * eNum + 1];
		}
		
		void add(int v, NetEdge e) {
			next[cnt] = head[v];
			edges[cnt] = e;
			head[v] = cnt++;
		}
		
		void addDirectedEdge(int from, int to, int capacity, int cost) {
			NetEdge forward = new NetEdge(from, to, capacity, cost);
			NetEdge back = new NetEdge(to, from, 0, -cost);
			forward.connect(back);
			back.connect(forward);
			this.add(from, forward);
			this.add(to, back);
		}
	}
	
	/*************************************************************** 
	 * Input 
	 **************************************************************/
	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	
	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	
	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
	
	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
	
	int[] nextIntArray(int size) throws IOException {
		int[] ret = new int [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextInt();
		return ret;
	}
	
	long[] nextLongArray(int size) throws IOException {
		long[] ret = new long [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextLong();
		return ret;
	}
	
	double[] nextDoubleArray(int size) throws IOException {
		double[] ret = new double [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextDouble();
		return ret;
	}
	
	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
	
	/*************************************************************** 
	 * Output 
	 **************************************************************/
	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}
	
	void printArray(int[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(long[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array, String spec) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}
	
	void printArray(Object[] array) {
		if (array == null || array.length == 0)
			return;
		boolean blank = false;
		for (Object x : array) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		if (collection == null || collection.isEmpty())
			return;
		boolean blank = false;
		for (Object x : collection) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	/*************************************************************** 
	 * Utility
	 **************************************************************/
	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory() >> 20) + "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}
	
	static void checkMemory() {
		System.err.println(memoryStatus());
	}
	
	static long prevTimeStamp = Long.MIN_VALUE;
	
	static void updateTimer() {
		prevTimeStamp = System.currentTimeMillis();
	}
	
	static long elapsedTime() {
		return (System.currentTimeMillis() - prevTimeStamp);
	}
	
	static void checkTimer() {
		System.err.println(elapsedTime() + " ms");
	}
	
	static void chk(boolean f) {
		if (!f) throw new RuntimeException("Assert failed");
	}
	
	static void chk(boolean f, String format, Object ... args) {
		if (!f) throw new RuntimeException(String.format(format, args));
	}
	
	static void writeLog(String format, Object ... args) {
		if (writeLog) System.err.println(String.format(Locale.US, format, args));
	}
	
	static void swap(int[] a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	static void swap(long[] a, int i, int j) {
		long tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	static void swap(double[] a, int i, int j) {
		double tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	static void shuffle(int[] a, int from, int to) {
		for (int i = from; i < to; i++)
			swap(a, i, rnd.nextInt(a.length));
	}
	
	static void shuffle(long[] a, int from, int to) {
		for (int i = from; i < to; i++)
			swap(a, i, rnd.nextInt(a.length));
	}
	
	static void shuffle(double[] a, int from, int to) {
		for (int i = from; i < to; i++)
			swap(a, i, rnd.nextInt(a.length));
	}
	
	static void shuffle(int[] a) {
		if (a == null) return;
		shuffle(a, 0, a.length);
	}
	
	static void shuffle(long[] a) {
		if (a == null) return;
		shuffle(a, 0, a.length);
	}
	
	static void shuffle(double[] a) {
		if (a == null) return;
		shuffle(a, 0, a.length);
	}
	
	static long[] getPartialSums(int[] a) {
		final long[] sums = new long [a.length + 1];
		for (int i = 0; i < a.length; i++)
			sums[i + 1] = sums[i] + a[i];
		return sums;
	}
	
	static long[] getPartialSums(long[] a) {
		final long[] sums = new long [a.length + 1];
		for (int i = 0; i < a.length; i++)
			sums[i + 1] = sums[i] + a[i];
		return sums;
	}
	
	static int[] getOrderedSet(int[] a) {
		final int[] set = Arrays.copyOf(a, a.length);
		if (a.length == 0) return set;
		shuffle(set);
		sort(set);
		int k = 1;
		int prev = set[0];
		for (int i = 1; i < a.length; i++) {
			if (prev != set[i]) {
				set[k++] = prev = set[i];
			}
		}
		return Arrays.copyOf(set, k);
	}
	
	static long[] getOrderedSet(long[] a) {
		final long[] set = Arrays.copyOf(a, a.length);
		if (a.length == 0) return set;
		shuffle(set);
		sort(set);
		int k = 1;
		long prev = set[0];
		for (int i = 1; i < a.length; i++) {
			if (prev != set[i]) {
				set[k++] = prev = set[i];
			}
		}
		return Arrays.copyOf(set, k);
	}
}

 



 



C Ticket HackerRank Solution


Copy Code Copied Use a different Browser

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int equal(double x,double y);
void init_labels();
void augment();
void update_labels();
void add_to_tree(int x, int prevx);
double hungarian();

#define N 510             //max number of vertices in one part
#define INF 100000000    //just infinity
#define E 0.0001
#define MAX 60000

double cost[N][N];          //cost matrix
int n, max_match;        //n workers and n jobs
double lx[N], ly[N];        //labels of X and Y parts
int xy[N];               //xy[x] - vertex that is matched with x,
int yx[N];               //yx[y] - vertex that is matched with y
int S[N], T[N];         //sets S and T in algorithm
double slack[N];            //as in the algorithm description
int slackx[N];           //slackx[y] such a vertex, that
                         // l(slackx[y]) + l(y) - w(slackx[y],y) = slack[y]
int prev[N];             //array for memorizing alternating paths
char dd[100][200],ds[200];
double price[100];
int d[500],ans[500];

int main(){
  double a=0;
  int nn,m,k,i,j,t;
  scanf("%d%d%d",&nn,&m,&k);
  for(i=0;i<k;i++)
    scanf("%s%lf",&dd[i][0],price+i);
  for(i=0;i<nn;i++){
    scanf("%s",ds);
    for(j=0;j<k;j++)
      if(strcmp(ds,&dd[j][0])==0){
        d[i]=j;
        break;
      }
  }
  n=nn+m;
  for(i=0;i<n;i++)
    for(j=0;j<n;j++){
      if(j<m || j<=i)
        cost[i][j]=0;
      else if(i<m || d[i-m]!=d[j-m])
        cost[i][j]=MAX-price[d[j-m]];
      else
        cost[i][j]=MAX-price[d[j-m]]*0.8;
    }
  a=hungarian();
  for(i=0;i<m;i++){
    if(equal(cost[i][xy[i]],0))
      continue;
    t=xy[i];
    while(1){
      ans[t-m]=i+1;
      if(equal(cost[t][xy[t]],0))
        break;
      t=xy[t];
    }
  }
  printf("%.3lf\n",MAX*(double)nn-a);
  for(i=0;i<nn;i++)
    printf("%d\n",ans[i]);
  return 0;
}
int equal(double x,double y){
  if(y-x<E && x-y<E)
    return 1;
  return 0;
}

void init_labels()
{
    int x,y;
    for(x=0;x<N;x++)
      lx[x]=ly[x]=0;
    //memset(lx, 0, sizeof(lx));
    //memset(ly, 0, sizeof(ly));
    for (x = 0; x < n; x++)
        for (y = 0; y < n; y++)
            //lx[x] = max(lx[x], cost[x][y]);
            lx[x]=(lx[x]>cost[x][y])?lx[x]:cost[x][y];
}

void augment()                         //main function of the algorithm
{
    if (max_match == n) return;        //check wether matching is already perfect
    int x, y, root;                    //just counters and root vertex
    int q[N], wr = 0, rd = 0;          //q - queue for bfs, wr,rd - write and read
                                       //pos in queue
    memset(S, 0, sizeof(S));       //init set S
    memset(T, 0, sizeof(T));       //init set T
    memset(prev, -1, sizeof(prev));    //init set prev - for the alternating tree
    for (x = 0; x < n; x++)            //finding root of the tree
        if (xy[x] == -1)
        {
            q[wr++] = root = x;
            prev[x] = -2;
            S[x] = 1;
            break;
        }

    for (y = 0; y < n; y++)            //initializing slack array
    {
        slack[y] = lx[root] + ly[y] - cost[root][y];
        slackx[y] = root;
    }
//second part of augment() function
    while (1)                                                        //main cycle
    {
        while (rd < wr)                                                 //building tree with bfs cycle
        {
            x = q[rd++];                                                //current vertex from X part
            for (y = 0; y < n; y++)                                     //iterate through all edges in equality graph
                if (equal(cost[x][y] , lx[x] + ly[y]) &&  !T[y])
                {
                    if (yx[y] == -1) break;                             //an exposed vertex in Y found, so
                                                                        //augmenting path exists!
                    T[y] = 1;                                        //else just add y to T,
                    q[wr++] = yx[y];                                    //add vertex yx[y], which is matched
                                                                        //with y, to the queue
                    add_to_tree(yx[y], x);                              //add edges (x,y) and (y,yx[y]) to the tree
                }
            if (y < n) break;                                           //augmenting path found!
        }
        if (y < n) break;                                               //augmenting path found!

        update_labels();                                                //augmenting path not found, so improve labeling
        wr = rd = 0;                
        for (y = 0; y < n; y++)        
        //in this cycle we add edges that were added to the equality graph as a
        //result of improving the labeling, we add edge (slackx[y], y) to the tree if
        //and only if !T[y] &&  slack[y] == 0, also with this edge we add another one
        //(y, yx[y]) or augment the matching, if y was exposed
            if (!T[y] &&  equal(slack[y] , 0))
            {
                if (yx[y] == -1)                                        //exposed vertex in Y found - augmenting path exists!
                {
                    x = slackx[y];
                    break;
                }
                else
                {
                    T[y] = 1;                                        //else just add y to T,
                    if (!S[yx[y]])    
                    {
                        q[wr++] = yx[y];                                //add vertex yx[y], which is matched with
                                                                        //y, to the queue
                        add_to_tree(yx[y], slackx[y]);                  //and add edges (x,y) and (y,
                                                                        //yx[y]) to the tree
                    }
                }
            }
        if (y < n) break;                                               //augmenting path found!
    }

    if (y < n)                                                          //we found augmenting path!
    {
        int cx,cy,ty;
        max_match++;                                                    //increment matching
        //in this cycle we inverse edges along augmenting path
        for (cx = x, cy = y; cx != -2; cx = prev[cx], cy = ty)
        {
            ty = xy[cx];
            yx[cy] = cx;
            xy[cx] = cy;
        }
        augment();                                                      //recall function, go to step 1 of the algorithm
    }
}//end of augment() function

void update_labels()
{
    int x, y;
    double delta = INF;             //init delta as infinity
    for (y = 0; y < n; y++)            //calculate delta using slack
        if (!T[y])
            //delta = min(delta, slack[y]);
            delta=(delta<slack[y])?delta:slack[y];
    for (x = 0; x < n; x++)            //update X labels
        if (S[x]) lx[x] -= delta;
    for (y = 0; y < n; y++)            //update Y labels
        if (T[y]) ly[y] += delta;
    for (y = 0; y < n; y++)            //update slack array
        if (!T[y])
            slack[y] -= delta;
}

void add_to_tree(int x, int prevx) 
//x - current vertex,prevx - vertex from X before x in the alternating path,
//so we add edges (prevx, xy[x]), (xy[x], x)
{
    int y;
    S[x] = 1;                    //add x to S
    prev[x] = prevx;                //we need this when augmenting
    for (y = 0; y < n; y++)    //update slacks, because we add new vertex to S
        if (lx[x] + ly[y] - cost[x][y] < slack[y])
        {
            slack[y] = lx[x] + ly[y] - cost[x][y];
            slackx[y] = x;
        }
}

double hungarian()
{
    double ret = 0;                      //weight of the optimal matching
    max_match = 0;                    //number of vertices in current matching
    memset(xy, -1, sizeof(xy));    
    memset(yx, -1, sizeof(yx));
    init_labels();                    //step 0
    augment();                        //steps 1-3
    int x;
    for (x = 0; x < n; x++)       //forming answer there
        ret += cost[x][xy[x]];
    return ret;
}

 

Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging

Leave a comment below

 

Related posts:

15 Days to learn SQL Hard SQL(Advanced)-SolutionBike Racers – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionTime Conversion – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionBalanced Brackets – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionNo Prefix Set – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionProblem solving – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionHuarongdao – HackerRank Solution
Tags: Cc++14full solutionGoHackerRank Solutionjavajava 15java 7java 8java8javascriptpypy 3Python 2python 3Ticket
ShareTweetPin
bhautik bhalala

bhautik bhalala

Related Posts

Leetcode All Problems Solutions
Code Solutions

Exclusive Time of Functions – LeetCode Solution

by admin
October 5, 2022
0
29

Exclusive Time of Functions - LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions...

Read more
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
32
Leetcode All Problems Solutions

Course Schedule III – LeetCode Solution

October 5, 2022
25
Leetcode All Problems Solutions

Maximum Product of Three Numbers – LeetCode Solution

September 11, 2022
52
Leetcode All Problems Solutions

Task Scheduler – LeetCode Solution

September 11, 2022
119
Leetcode All Problems Solutions

Valid Triangle Number – LeetCode Solution

September 11, 2022
28
Next Post
15 Days to learn SQL Hard SQL(Advanced)-Solution

DFS Edges - HackerRank Solution

15 Days to learn SQL Hard SQL(Advanced)-Solution

Diameter Minimization - HackerRank Solution

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

You may also like

15 Days to learn SQL Hard SQL(Advanced)-SolutionBike Racers – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionTime Conversion – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionBalanced Brackets – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionNo Prefix Set – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionProblem solving – HackerRank Solution 15 Days to learn SQL Hard SQL(Advanced)-SolutionHuarongdao – HackerRank Solution

Categories

  • Algorithms
  • Anime
  • Biography
  • Business
  • Code Solutions
  • Cosmos
  • Countdowns
  • Culture
  • Economy
  • Education
  • Entertainment
  • Finance
  • Games
  • Hackerrank
  • Health
  • How to
  • Investment
  • LeetCode
  • Lifestyle
  • LINUX SHELL
  • Manga
  • News
  • Opinion
  • Politics
  • Sports
  • SQL
  • Tech
  • Travel
  • Uncategorized
  • Updates
  • World
  • DMCA
  • Home
  • My account
  • Privacy Policy
  • Top Posts

Recent Blogs

Leetcode All Problems Solutions

Exclusive Time of Functions – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions

Smallest Range Covering Elements from K Lists – LeetCode Solution

October 5, 2022
Leetcode All Problems Solutions
Code Solutions

Majority Element II – LeetCode Solution

September 6, 2022
23
Biography

Raashi Khanna Net Worth, Age, Height , Achivements and more

September 8, 2022
0
The Girl From Plainville
Entertainment

The Girl From Plainville Episode 9 Countdown , Release Date

May 5, 2022
10
15 Days to learn SQL Hard SQL(Advanced)-Solution
Algorithms

Stone Piles – HackerRank Solution

August 24, 2022
8

© 2022 ZeroPlusFour - Latest News & Blog.

No Result
View All Result
  • Home
  • Category
    • Business
    • Culture
    • Economy
    • Lifestyle
    • Health
    • Travel
    • Opinion
    • Politics
    • Tech
  • Landing Page
  • Support Forum
  • Contact Us

© 2022 ZeroPlusFour - Latest News & Blog.

Welcome Back!

Login to your account below

Forgotten Password?

Retrieve your password

Please enter your username or email address to reset your password.

Log In
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept All”, you consent to the use of ALL the cookies. However, you may visit "Cookie Settings" to provide a controlled consent.
Cookie SettingsAccept All
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT
Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?