In this 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. The n people are in a queue.
There are m ticket windows from which tickets can be purchased. Then n people will be distributed in the windows such that the order is maintained. In other words, suppose we number the people 1 to n from front to back. If the person I and person j go to the same window and i<j, then the 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.
Try to distribute the n people across the m windows such that the total cost S paid by all n people is minimized.
Problem solution in Java.
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();
}
}
Problem solution in C++.
#include <algorithm>
#include <climits>
#include <iostream>
#include <map>
#include <string>
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';
}Problem solution in C.
#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;
}
1 Comments
Hack ticket rank
ReplyDelete