I don't know what kind of technique required for this problem. Could anyone please point it out? Thank you so much in advance!
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. -----> Edit: One person can only be in one room.
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:
The company has at least 1 room.
The company's efficiency is exactly E.
The number of people in the company (let's say N) is minimum.
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).
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 A2 B1 B2 B3 (Efficiency = 2 * 3 = 6)
A3 B4 (Efficiency = 1 * 1 = 1)
The total efficiency is 6 + 1 = 7.
Constraints:
- 1 <= E <= 10,000
Link to the problem: LEM7
Oh, sorry. I've got it. Rather difficult to understand=)
Oops, my bad! I've just edited the problem. I misunderstood it in the first place. With the new modification, I came up with a DP solution:
Let's say f[i] is the result when E = i. Because of conditions 3, 4 and 5, we have to consider: f[i].N, f[i].S, f[i].K.
1. For the case
f[i].K = 1We can find the rest: f[i].N and f[i].S by taking:
i = p * q ----> f[i].N = min(p + q) and f[i].S = min(p, q) with the exact order: N then S
------> O(E * sqrt(E))
2. For the case
f[i].K >= 2f[i] = min(f[j] + f[i - j]) (j < i)('+' operation means: .N + .N, .S + .S, .K + .K, with the exact order: N then S and then K)
-----> O(E^2)
I'm just being curious if there's any other better solution with a smaller complexity? Thank you very much in advance!
E2 with constant approximately
is just 25000000. It should pass tests. Or you can simply precalculate all answers and paste them in your code.
ADD: My implementation passed all tests.