HackerRank Ticket Problem Solution Yashwant Parihar, June 2, 2023May 28, 2024 In this post, we will solve HackerRank Ticket Problem Solution.There are n people at the railway station, and each one wants to buy a ticket to go to one of k different destinations. Then people are in a queue.There are m ticket windows from which tickets can be purchased. Then people will be distributed in the windows such that the order is maintained. In other words, suppose we number the people 1 ton from front to back. If person i and person j go to the same window and i < j, then person i should still be ahead of person j in the window.Each ticketing window has an offer. If a person in the queue shares the same destination as the person immediately in front of him/her, a 20% reduction in the ticket price is offered to him/her.For example, suppose there are 3 people in the queue for a single ticket window, all with the same destination which costs 10 bucks. Then the first person in the queue pays 10 bucks, and the 2nd and 3rd persons get a discount of 20% on 10 bucks, so they end up paying 8 bucks each instead of 10 bucks.Try to distribute then people across the m windows such that the total cost $ paid by all n people is minimized.Input FormatThe first line contains 3 integers:n is the number of peoplem is the number of ticket windowsk is the number of destinations separated by a single space (in the same order)Then k lines follow. The ith line contains an alphanumeric string place, and an integer price:place, is the ith destinationprice, is the ticket price for place.Then n lines follow. The ith line contains an alphanumeric string destination, which is the destination of the ith person.Sample Input5 2 3 CALIFORNIA 10 HAWAII 8 NEWYORK 12 NEWYORK NEWYORK CALIFORNIA NEWYORK HAWAII Sample Output49.2 1 1 2 1 1ExplanationAt the beginning, all the people are in the same queue, and will go to the ticket windows one by one in the initial order.{1, 2, 4, 5} will buy ticket in the first window.{3} will buy ticket in the second window.In the first ticket window, #1 will pay 12 bucks to go to NEWYORK, and #2 and #4 have the same destination with the person in front of them, so they will get 20% off, and will pay 9.6 bucks each. #5 has a different destination, so it will cost him 8 bucks to go to HAWAII.In the second ticket window, #3 will pay 10 bucks to go to CALIFORNIA.HackerRank Ticket Problem SolutionTicket C Solution#include<stdio.h> #include<stdlib.h> #include<string.h> #define N 510 #define INF 100000000 #define E 0.0001 #define MAX 60000 double cost[N][N], lx[N], ly[N], slack[N], price[100]; int n, max_match, xy[N], yx[N], S[N], T[N], slackx[N], prev[N], d[500], ans[500]; char dd[100][200], ds[200]; 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; } for( x = 0 ; x < n ; x++ ) { for( y = 0 ; y < n ; y++ ) { lx[x] = ( lx[x] > cost[x][y] ) ? lx[x] : cost[x][y]; } } } void augment() { if( max_match == n ) { return; } int x, y, root, q[N], wr = 0, rd = 0; memset(S, 0, sizeof(S)); memset(T, 0, sizeof(T)); memset(prev, -1, sizeof(prev)); for( x = 0 ; x < n ; x++ ) { if( xy[x] == -1 ) { q[wr++] = root = x; prev[x] = -2; S[x] = 1; break; } } for( y = 0 ; y < n ; y++ ) { slack[y] = lx[root] + ly[y] - cost[root][y]; slackx[y] = root; } while(1) { while( rd < wr ) { x = q[rd++]; for( y = 0 ; y < n ; y++ ) { if( equal(cost[x][y] , lx[x] + ly[y]) && !T[y] ) { if( yx[y] == -1 ) { break; } T[y] = 1; q[wr++] = yx[y]; add_to_tree(yx[y], x); } } if( y < n ) { break; } } if( y < n ) { break; } update_labels(); wr = rd = 0; for( y = 0 ; y < n ; y++ ) { if( !T[y] && equal(slack[y] , 0) ) { if( yx[y] == -1 ) { x = slackx[y]; break; } else { T[y] = 1; if(!S[yx[y]]) { q[wr++] = yx[y]; add_to_tree(yx[y], slackx[y]); } } } } if( y < n ) { break; } } if( y < n ) { int cx, cy, ty; max_match++; for( cx = x, cy = y ; cx != -2 ; cx = prev[cx], cy = ty ) { ty = xy[cx]; yx[cy] = cx; xy[cx] = cy; } augment(); } } void update_labels() { int x, y; double delta = INF; for( y = 0 ; y < n ; y++ ) { if(!T[y]) { delta = ( delta < slack[y] ) ? delta : slack[y]; } } for( x = 0 ; x < n ; x++ ) { if(S[x]) { lx[x] -= delta; } } for( y = 0 ; y < n ; y++ ) { if(T[y]) { ly[y] += delta; } } for( y = 0 ; y < n ; y++ ) { if(!T[y]) { slack[y] -= delta; } } } void add_to_tree(int x, int prevx) { int y; S[x] = 1; prev[x] = prevx; for( y = 0 ; y < n ; y++ ) { 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; max_match = 0; memset(xy, -1, sizeof(xy)); memset(yx, -1, sizeof(yx)); init_labels(); augment(); int x; for( x = 0 ; x < n ; x++ ) { ret += cost[x][xy[x]]; } return ret; } 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; }Ticket C++ Solution/*Ticket*/ #include <bits/stdc++.h> using namespace std; #define REP(i, n) for (int i = 0; i < (n); i++) #define SIZE(x) (sizeof(x)/sizeof(*x)) const int N = 500, V = N*2+2; const double EPS = 1e-8; string dest[N]; bool in[V]; int q[V], window[N]; double dist[V]; struct Edge { int v, c; double w; Edge *next, *twain; } *es[V], *pred[V], pool[N*(N-1)+3*N << 1], *allo = pool; void add(int u, int v, int c, double w) { allo[0] = {v, c, w, es[u], allo+1}; allo[1] = {u, 0, - w, es[v], allo}; es[u] = allo++; es[v] = allo++; } bool labelCorrecting(int n, int src, int sink) { fill_n(in, n, false); fill_n(pred, n, nullptr); fill_n(dist, n, numeric_limits<double>::max()); dist[src] = 0; int *fr = q, *re = q; *re++ = src; while (fr != re) { int u = *fr++; if (fr == q+SIZE(q)) fr = q; in[u] = false; for (Edge *e = es[u]; e; e = e->next) if (e->c > 0) { double t = dist[u]+e->w; if (t+EPS < dist[e->v]) { dist[e->v] = t; pred[e->v] = e; if (! in[e->v]) { in[e->v] = true; *re++ = e->v; if (re == q+SIZE(q)) re = q; } } } } return dist[sink] < numeric_limits<double>::max(); } double minCostMaxFlow(int n, int src, int sink, int m) { int flow = 0; double cost = 0; while (flow < m && labelCorrecting(n, src, sink) && dist[sink] < 0) { int f = m-flow; for (int v = sink; v != src; v = pred[v]->twain->v) f = min(f, pred[v]->c); flow += f; cost += f*dist[sink]; for (int v = sink; v != src; v = pred[v]->twain->v) { pred[v]->c -= f; pred[v]->twain->c += f; } } return cost; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; map<string, int> price; REP(i, k) { int p; cin >> dest[0] >> p; price[dest[0]] = p; } int src = 2*n, sink = src+1; REP(i, n) { cin >> dest[i]; double t = price[dest[i]]; add(src, i, 1, t); add(i, n+i, 1, -100*n); add(n+i, sink, 1, 0); REP(j, i) add(n+j, i, 1, dest[j] == dest[i] ? 0.8*t : t); } cout << minCostMaxFlow(sink+1, src, sink, m)+100*n*n << '\n'; int id = 0; for (Edge *e = es[src]; e; e = e->next) if (e->c == 0) window[e->v] = ++id; REP(i, n) for (Edge *e = es[n+i]; e; e = e->next) if (e->v < n && i < e->v && e->c == 0) window[e->v] = window[i]; REP(i, n) cout << window[i] << '\n'; }Ticket C Sharp Solutionusing System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using System.Diagnostics; class MCMF { public const int MAXV=10000; public const long inff = 0x3f3f3f3f; public const long infc = 0x3f3f3f3f; int nv, ne, src, sink; int[] from, to, next, Q = new int[MAXV], head = new int[MAXV], prev = new int[MAXV], pe = new int[MAXV]; long[] flow, cap, cost, d=new long[MAXV]; bool[] InQ = new bool[MAXV]; public MCMF(int n, int s, int t) { int MAXE = Math.Min( n*n,500000); from=new int[MAXE]; to=new int[MAXE]; next = new int[MAXE]; flow = new long[MAXE]; cap=new long[MAXE]; cost=new long[MAXE]; nv = n; src = s; sink = t; ne = 0; for(int i = 0; i < nv; i++) head[i] = -1; } public void add(int u, int v, long c, long w) { from[ne] = u; to[ne] = v; cap[ne] = c; cost[ne] = +w; flow[ne] = 0; next[ne] = head[u]; head[u] = ne++; from[ne] = v; to[ne] = u; cap[ne] = 0; cost[ne] = -w; flow[ne] = 0; next[ne] = head[v]; head[v] = ne++; } bool spfa() { for(int i = 0; i < nv; i++) { prev[i] = -1; InQ[i] = false; d[i] = infc; } d[src] = 0; InQ[src] = true; Q[0] = src; int f = 0,r = 1; while(f != r) { int x = Q[f++]; if(f == MAXV) f = 0; InQ[x] = false; if(x == sink) continue; for(int k = head[x]; k != -1; k = next[k]) { int y = to[k]; if(flow[k] < cap[k] && d[y] > cost[k] + d[x]) { d[y] = cost[k] + d[x]; if(!InQ[y]) { InQ[y] = true; Q[r++] = y; if(r == MAXV) r = 0; } prev[y] = x; pe[y] = k; } } } return -1 != prev[sink]; } public long minCostmaxFlow() { long mflow=0, mcost=0; while (spfa()) { var expand = inff; for(int k = sink; k != src; k = prev[k]) if(expand > cap[pe[k]] - flow[pe[k]]) expand = cap[pe[k]] - flow[pe[k]]; for(int k = sink; k != src; k = prev[k]){ flow[pe[k]] += expand; flow[pe[k] ^ 1] -= expand; } if(d[sink] >= 0) break; mflow += expand; mcost += d[sink] * expand; } return mcost; } public int[] Prev() { var prev = new int[nv]; for (int i = 0; i < ne; i++) { int from = this.from[i] / 2; int to = this.to[i] / 2; if (flow[i] > 0) prev[to] = from; } return prev; } }; // static class Program { static void Main(string[] args) { # if DEBUG Console.SetIn(new StreamReader(args[0])); var t0 = DateTime.Now; # endif var s = Console.ReadLine().Trim().Split(); var n_people=int.Parse(s[0]); var n_window=int.Parse(s[1]); var n_dest = int.Parse(s[2]); Dictionary<string, int> map=new Dictionary<string,int>(); var price_1 = new int[n_dest]; var price_2 = new int[n_dest]; for (int i = 0; i < n_dest; i++) { s = Console.ReadLine().Trim().Split(); map[s[0]] = i; var p = int.Parse(s[1]); price_2[i] = p * 8; price_1[i] = p * 10; } var dest = new int[n_people]; for (int i = 0; i < n_people; i++) dest[i] = map[Console.ReadLine().Trim()]; // int S1 = 2 * n_people, S = S1 + 1, T = S + 1; var mm=new MCMF(T + 1, S, T); mm.add(S, S1, n_window, 0); for (int i = 0; i < n_people; i++) mm.add(2 * i, 2 * i + 1, 1, -MCMF.infc); for (int i = 0; i < n_people; i++) mm.add(S1, 2 * i, 1, price_1[dest[i]]); for (int i = 0; i < n_people; i++) mm.add(2 * i + 1, T, 1, 0); for (int i = 0; i < n_people; i++) for (int j = i + 1; j < n_people; j++) { if (dest[i] == dest[j]) mm.add(2 * i + 1, 2 * j, 1, price_2[dest[j]]); else mm.add(2 * i + 1, 2 * j, 1, price_1[dest[j]]); } var cost = mm.minCostmaxFlow(); var ret = cost + n_people * MCMF.infc; Console.WriteLine(ret / 10.0); var prev = mm.Prev(); int[] id = new int[n_people]; for (int ct=1,i = 0; i < n_people; i++) if (prev[i] >= n_people) id[i] = ct++; else id[i] = id[prev[i]]; foreach (var i in id) Console.WriteLine(i); # if DEBUG Console.WriteLine(DateTime.Now.Subtract(t0)); # endif } }Ticket Java Solutionimport java.io.*; import java.text.DecimalFormat; import java.util.*; public class Solution { static class Edge { int v; int c; double w; Edge next; Edge twain; public Edge(int v, int c, double w) { this.v = v; this.c = c; this.w = w; } } static Edge[] es; static Edge[] pred; static Edge[] pool; static int allo = 0; static void add(int u, int v, int c, double w) { Edge e1 = new Edge(v, c, w); Edge e2 = new Edge(u, 0, -w); pool[allo] = e1; pool[allo].next = es[u]; pool[allo].twain = e2; pool[allo+1] = e2; pool[allo+1].next = es[v]; pool[allo+1].twain = e1; es[u] = pool[allo++]; es[v] = pool[allo++]; } static final double EPS = 1e-8; static boolean[] in; static int[] q; static double[] dist; static boolean labelCorrecting(int n, int src, int sink) { Arrays.fill(in, 0, n, false); Arrays.fill(pred, 0, n, null); Arrays.fill(dist, 0, n, Double.MAX_VALUE/2); dist[src] = 0; int fr = 0; int re = 0; q[re++] = src; while (fr != re) { int u = q[fr++]; if (fr == q.length) { fr = 0; } in[u] = false; for (Edge e = es[u]; e != null; e = e.next) { if (e.c > 0) { double t = dist[u]+e.w; if (t + EPS < dist[e.v]) { dist[e.v] = t; pred[e.v] = e; if (! in[e.v]) { in[e.v] = true; q[re++] = e.v; if (re == q.length) re = 0; } } } } } return dist[sink] < Double.MAX_VALUE; } static double minCostMaxFlow(int n, int src, int sink, int m) { int flow = 0; double cost = 0; while (flow < m && labelCorrecting(n, src, sink) && dist[sink] < 0) { int f = m-flow; for (int v = sink; v != src; v = pred[v].twain.v) { f = Math.min(f, pred[v].c); } flow += f; cost += f*dist[sink]; for (int v = sink; v != src; v = pred[v].twain.v) { pred[v].c -= f; pred[v].twain.c += f; } } return cost; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); Map<String, Integer> price = new HashMap<>(); for (int i = 0; i < k; i++) { st = new StringTokenizer(br.readLine()); String s = st.nextToken(); int p = Integer.parseInt(st.nextToken()); price.put(s, p); } int src = 2*n; int sink = src+1; String[] dest = new String[n]; es = new Edge[n*2+2]; pred = new Edge[n*2+2]; pool = new Edge[n*(n-1)+3*n << 1]; for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); String s = st.nextToken(); dest[i] = s; double t = price.get(s); add(src, i, 1, t); add(i, n+i, 1, -100*n); add(n+i, sink, 1, 0); for (int j = 0; j < i; j++) { add(n+j, i, 1, dest[j].equals(dest[i]) ? 0.8*t : t); } } in = new boolean[n*2+2]; q = new int[n*2+2]; dist = new double[n*2+2]; double res = minCostMaxFlow(sink+1, src, sink, m)+100*n*n; DecimalFormat df = new DecimalFormat("#.###"); bw.write(df.format(res) + "\n"); int id = 0; int[] window = new int[n]; for (Edge e = es[src]; e != null; e = e.next) { if (e.c == 0) { window[e.v] = ++id; } } for (int i = 0; i < n; i++) { for (Edge e = es[n+i]; e != null; e = e.next) { if (e.v < n && i < e.v && e.c == 0) { window[e.v] = window[i]; } } } for (int i = 0; i < n; i++) { bw.write(window[i] + "\n"); } bw.newLine(); bw.close(); br.close(); } } c C# C++ HackerRank Solutions java CcppCSharpHackerrank Solutionsjava