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

×

CALLSCHE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Maksym Bevza
Tester: Istvan Nagy
Editorialist: Miguel Oliveira

DIFFICULTY:

Medium

PREREQUISITES:

Graph Theory, Minimum Cut, Maximum Flow

PROBLEM:

Consider that there are D business days, each with N working hours. The availability of each of the P employees is given for each hour of the business days. The employees also need to have at least 1 hour for lunch in a given time interval.

Given a call center schedule constraints, find if it's possible to make a schedule for all employees so that there are always a given number of employees available to talk with clients, satisfying the constraints.

EXPLANATION:

Subtask1

N, H, D and P are really small. We can brute force to see if there is a feasible solution.

Subtask 2

Same as subtask 3 but with an inefficient implementation.

Subtask 3

The problem involves deciding, for each person, what activity they will do in each hour of the day, satisfying some restrictions. This resembles an assignment problem. In fact, we can use a similar approach to assignment problems based on network flow.

We can model this problem as a graph where the vertices represent people, person i talking to clients or having lunch, and the edges contain the given constraints.

A constraint of the form 'person x must not talk to clients more than $L_x$ hours per week' can be modelled as an edge with capacity $L_x$.

Now the tricky part is the lunch time.

There are N hours in each day and we must guarantee there is a free hour during lunch time. To do this, we create 2 nodes per person and per day: "lunch hours at day d" and "normal hours at day d".

Suppose $\Delta_{LT} = {LT}*{end} - {LT}*{begin} - meetings$, the number of lunch hours not filled with meetings. Then, we have $N - \Delta_{LT} - meetings$ normal hours and $\Delta_{LT}$ free lunch hours. In order to have a free lunch hour, $\Delta_{LT}$ must be positive. One of these must not be filled with meetings nor clients, so the actual capacity associated with lunch hours is $\Delta_{LT} - 1$. This way, we ensure that at least 1 of these hours is not assigned work.

Now, we create nodes for each pair (day, hour) and connect these with the nodes associated with each <person, normal="" lunch="" hours=""> if the person does not have meeting during that hour in that day: $F_{k, i, j} = 1$.

Finally, we connect the (day, hour) nodes with a sink vertex with capacity equal to $R_{i, j}$.

Suppose we have 5 days: monday - friday, with H = 5 and lunch hours at hours 3 and 4. A possible resulting graph is the following

If the minimum cut between vertices S and T equals $\sum_{R_{i, j}}$ then we can satisfy all customer requirements.

The minimum cut can be calculated using an efficient maximum flow algorithm such as Dinic's algorithm.

Sample Solutions

Author
Tester

This question is marked "community wiki".

asked 16 Feb '16, 00:18

mogers's gravatar image

5★mogers
659716
accept rate: 25%

edited 18 Feb '16, 22:21

admin's gravatar image

0★admin ♦♦
19.8k350498541


So... $O(MAX^2)$ vertices, $O(MAX^3)$ edges, $O(MAX^7)$ Dinic?

Ford-Fulkerson is better. The asymptotic complexity is $O(15\cdot MAX^5)$ and in practice, a DFS-based implementation of looking for a path from the source to the sink and stopping the DFS as soon as a path is found is quite fast.

link

answered 16 Feb '16, 03:38

xellos0's gravatar image

7★xellos0
5.9k54292
accept rate: 10%

The worst case time complexity is a bit misleading in these flow algorithms, especially in these kind of networks. While I did not test thoroughly, from what I've seen, Dinic's algorithm performs faster than Ford-Fulkerson in this problem.

(16 Feb '16, 04:34) mogers5★

A sample of 15 tests, some of which can be solved using some necessary condition, isn't good enough to measure the speed. In addition, it depends on how many optimisations are made - I'm sure either could seem faster than the other based on it. But it's still good to note the complexities, if only for a theoretical purpose.

Anyway, I have never encountered a flow problem unsolvable by Ford-Fulkerson.

(16 Feb '16, 07:10) xellos07★

Please someone tell whether greedy solution would be correct for this problem or not as I got an AC using greedy technique in O(n^3) complexity. AC Solution .

link

answered 16 Feb '16, 04:53

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

Can you describe the idea of your greedy algorithm ? Its painful to look at some code and derive the idea out of it.

(17 Feb '16, 22:48) thezodiac19946★
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,684
×2,598
×1,219
×114
×107
×20

question asked: 16 Feb '16, 00:18

question was seen: 2,381 times

last updated: 18 Feb '16, 22:21