MKWRK - Editorial

editorial
, ,
1

Problem Link:

https://www.codechef.com/CDSO2016/problems/MKWRK

Difficulty:

Medium

Pre-requisites:

Sorting

Problem:

There is a company having E employees working in town T that you work for. The employees live in N towns in that
area. Some of the employees drive P passengers. When P==1 then it means the driver can only transport themselves to work. You want to ensure that everyone will be able to make it to work and you would like to minimize the number of cars on the road.

You want to calculate the number of cars on the road, with these requirements:

• Every employee can get to town T.

• The only way an employee may travel between towns is in a car belonging to an employee.

• Employees can only take rides from other employees that live in the same town.

• The minimum number of cars is used.

Find whether it is possible for everyone to make it to work, and if it is, how many cars will end up driving to the office.

Explanation:

From the problem statement we can interpret the following rules to find the number of cars from a given town:

• If there are no employees in a town, we don’t need any cars

• If the town is the location of the office, we don’t need any cars

• If there are employees, and this is not the location of the office, we need cars

• Employees who are drivers can only carry passengers to work from their hometown

The exact number of cars we are told should be the minimum number capable of carrying all the employees from the town. To find this number, sort the employees based on their passenger capacity and sum the capacities until you reach a number greater than or equal to the number of employees in the town. If summing all of the passenger capacities results in a smaller number than the employee headcount, then a solution is impossible. In pseudocode:

int[] employees; // The passenger capacity of each employee.

reverseSort(employees); // sort from high to low

int capacity = 0;

for (int i = 0; i < employees.length; i++) {

capacity += employees[i];

if (capacity >= employees.length)

    return i;

}

return “IMPOSSIBLE”