You are not logged in. Please login at www.codechef.com to post your questions!

×

CDVA1608 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Aditya Kumar
Tester: Ashutosh Kumar
Editorialist: Aditya Kumar

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Graph, Single Source Shortest Path (Dijkstra Algorithm), Bipartite Matching, MAX FLOW

PROBLEM:

Given a graph whoes each node represents a building and edges represents roads connceting them. At each building there exists a passenger or a taxi driver, except at the Movie theatre. Each taxi driver will take only one passenger and will drive for limited amount of time. Your task is to compute maximum number of passenger reaching the theatre. Given, each passenger wants to go to the theatre and can approach to any taxi driver.

QUICK EXPLANATION:

Create a bipartite graph in which first set is for taxi drivers and second one is for passengers. Draw an edge between a taxi driver and a passenger, if and only if, that taxi driver can drop that passenger at the theatre within his driving time. You can use any single source shortest path for this purpose. Now you have a graph, you just need to find maximal matching in it.

EXPLANATION:

This problem can is divided into two parts: Building graph and computing the Maximum flow.

Creation of Graph:

We can see that each taxi driver can be approached by all the passengers, but there is a driving time limit for each driver. So, we construct a graph (bipartite) containing two set of nodes, first set for taxi driver and second one for passengers.

How to draw edges in the graph?

Let's take a passenger j and driver i. There exist an edge in the graph between them, if and only if, the taxi driver drops the passenger to the theatre, i.e., $T[i] * S[i] >= (distTaxi[i][j] + distTh[j])$, where $T[i]$, $S[i]$ and $distTaxi[i][j]$ represents driving time, speed, and minimum distance (between $i_{th}$ driver and $j_{th}$ passenger) of the $i_{th}$ driver respectively. $distTh[j]$ represents the minimum distance between $j_{th}$ passenger and Movie theatre. To compute distTh for all passenger, apply SSSP (single sourse shortest path, [Dijkstra Algorithm]) from the Movie theatre. Also, for distTaxi apply SSSP from each taxi driver.

    for each i as taxi driver:
        capacity = S[i] * T[i]
        for each j as passenger:
            totaldist = distTh[j] + distTaxi[i][j]
            if totaldist <= capacity:
                We have an edge from i to j.

Computing Max Flow

Our build graph looks like the one below.

Once our graph is build, you just need to compute how many maximum number of edges that you can use to reach the theatre, considering atmost one outgoing edge can be present from each driver, i.e., finding maximal matching of this graph.
Time limit is a bit strict so use fast algorithm for maximal matching and SSSP.

OPTIMAL COMPLEXITY:

$\mathcal{O}(N*R\log(N+P+1) + N*P)$

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution will be uploaded soon.

RELATED PROBLEMS:

TAXI
Dungeon of Death

This question is marked "community wiki".

asked 30 Mar '16, 00:28

adi28galaxyak's gravatar image

5★adi28galaxyak
1164
accept rate: 14%

edited 30 Mar '16, 14:47

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,298
×179
×114
×86
×34
×4

question asked: 30 Mar '16, 00:28

question was seen: 972 times

last updated: 30 Mar '16, 14:47