HackerRank Ticket problem solution

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("%.3lfn", MAX * (double)nn - a);
    for( i = 0 ; i <nn ; i++ )
    {
        printf("%dn", ans[i]);
    }
    return 0;
}