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
#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
/* 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
#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