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.

![](upload://glY2sLWCjvprnOcEZl1grGcJBtH.png)

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

![](upload://nslFG268NNndsadH9YCtGtrY0Ht.jpeg)

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

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.

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.

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 .

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.

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

//