HackerRank Ticket Problem Solution

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

Explanation
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();
  }
}

c C# C++ HackerRank Solutions java C cpp CSharp Hackerrank Solutions java