A Hard Dynamic Programming Problem

general
, ,
1

Could anyone who’s good at dynamic programming please help me on this problem?

There are several rooms in a company. In each room, there are some employers and some employees, and there is no one who’s both an employer and an employee. One person can be in many rooms, but two people cannot be in the same two rooms. In a room, every employer gives work to their employees, but the employers do not give work to each other. The efficiency of a room is determined by the “relationship” in that room.

Example: If there are 2 employers and 3 employees in a room, that room’s efficiency will be 6 (= 2 * 3).

The company’s efficiency is the total efficiency of all rooms.

Write a program to organize the company such that these conditions are met:

  1. The company has at least 1 room.
  2. The company’s efficiency is exactly E.
  3. The number of people in the company (let’s say N) is minimum.
  4. If there are more than 1 solution to get all the first 3 conditions satisfied, find the solution that has the minimum number of employers (let’s say S).
  5. If there are more than 1 solution to get all the first 4 conditions satisfied, find the solution that has the minimum number of rooms (let’s say K).

Example:

Input:

7 (E)

Output:

7 3 2 (N S K)

Explanation:

There are 3 employers (A1, A2, A3) and 4 employees (B1, B2, B3, B4). They can be put into 2 rooms:

  • A1 B1 B2 B3 (Efficiency = 1 * 3 = 3)
  • A2 A3 B1 B4 (Efficiency = 2 * 2 = 4)

The total efficiency is 3 + 4 = 7.

Constraints:

1 <= E <= 10,000

Link to the problem: SPOJ.com - Problem LEM7

1 Like