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 Format
The first line contains 3 integers:
- n is the number of people
- m is the number of ticket windows
- k 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 destination
- price, 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 Input
5 2 3
CALIFORNIA 10
HAWAII 8
NEWYORK 12
NEWYORK
NEWYORK
CALIFORNIA
NEWYORK
HAWAII
Sample Output
49.2
1
1
2
1
1Explanation
At 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.
Ticket 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 Solution
using 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 Solution
import 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();
}
}
