Problem Statement |
| | We are building an application using different types of components. Each time we want to install a new component, we choose one randomly (yes, it is crazy). Each of the n types of components has an equal probability 1/n of being chosen. There is an infinite number of each type.
Each time we choose a component instance, we first determine if it can be installed. Some components may require one or more other types of components to already be installed. If all the required components are not currently installed, we cannot install the chosen component.
If the chosen component can be installed, we then decide whether or not to actually install it. Each component has an associated income and expense. The expense is the amount of money we must spend to install the component, and the income is the amount of money the installed component is expected to give us. Our goal is to maximize the expected total profit (all our income minus all our expenses). If we decide to install a chosen component, we must install it immediately (i.e., we can't put it aside and use it later).
Multiple instances of the same component type can be installed in the application. Each instance costs the same amount of money and has the same expected income. Note that once all the requirements for a component have been met, we may install multiple instances of that component type. For example, consider the case where component type 5 requires component type 3, and a single instance of component type 3 is currently installed. Every time we choose component type 5 from now on, we are allowed to install an instance of it. We do not require an instance of component type 3 for each instance of component type 5.
You are given an int k, the number of times we randomly choose a new component. You are also given a String[] components, where the i-th element (0-indexed) contains the requirements for component type i. Each element is a single space separated list of the component's required component types. You are given int[]s income and expense, where the i-th elements are the income and expense, respectively, associated with component type i. We will use an optimal strategy and always try to maximize our expected total profit when deciding whether or not to install chosen components (so, if installing a component lowers our expected total profit, we don't install it). Return our expected total profit. |
| |
Definition |
| | | Class: | CrazyComponents | | Method: | expectedProfit | | Parameters: | int, String[], int[], int[] | | Returns: | double | | Method signature: | double expectedProfit(int k, String[] components, int[] income, int[] expense) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | A return value with either an absolute or relative error of less than 1.0E-9 is considered correct. |
| |
Constraints |
| - | k will be between 1 and 50, inclusive. |
| - | components will contain between 1 and 15 elements, inclusive. |
| - | components, income and expense will each contain the same number of elements. |
| - | Each element of components will be a single space separated list of integers, without leading or trailing spaces. |
| - | Each integer in each element of components will be between 0 and n-1, inclusive, with no extra leading zeroes, where n is the number of elements in components. |
| - | The list described by element i of components will not contain i. |
| - | In each element of components, integers will be distinct. |
| - | Each element of income will be between 0 and 1000000, inclusive. |
| - | Each element of expense will be between 0 and 1000000, inclusive. |
| |
Examples |
| 0) | |
| | 1 | { "", "" } | { 1, 2 } | { 0, 0 } |
| Returns: 1.5 | | Here, we choose a component only once. If we choose component type 0, our profit is 1 - 0 = 1. If we choose component type 1, our profit is 2 - 0 = 2. Since each type is equally likely to be chosen, the expected profit is 0.5 * 1 + 0.5 * 2. |
|
|
| 1) | |
| | 2 | { "1", "" } | { 10, 0 } | { 0, 2 } |
| Returns: 1.5 | | If we pick component 0 in the first turn (1/2 probability), we won't be able to install it. Whichever component we pick after that, it's better not to install it and settle for 0 profit.
On the other hand, if we pick component 1 in the first turn (1/2 probability), we should install it even though the net is -2. If on the second try we pick component 1 again (1/4 total probability), we don't install it and end up losing the 2 we already spent. However, if we pick component 0 on the second try (1/4 total probability), we can install it and earn 10 for a total profit of 8. The expected profit is 1/4 * (-2) + 1/4 * 8 = 1.5.
|
|
|
| 2) | |
| | 3 | { "1 2", "", "" } | { 100, 0, 0 } | { 0, 0, 0 } |
| Returns: 7.407407407407408 | | Component 0 (the only one that makes a profit) requires components 1 and 2 to be already installed, so if we draw it in the first or in the second turn, we won't be able to install it. It is only possible to install it in the 3rd turn, supposing that in the 1st and 2nd turns we drew components 1 and 2. The probability that we will have components 1 and 2 installed after the 2nd turn is 2/3 * 1/3 = 2/9. The probability of then picking component 0 is 1/3, so our expected profit equals 2/9 * 1/3 * 100 = 7.407... . |
|
|
| 3) | |
| | 5 | { "1", "2", "0", "" } | { 4, 5, 6, 7 } | { 0, 0, 0, 8 } |
| Returns: 0.0 | |
|
| 4) | |
| | 10 | { "", "", "", "", "", "", "", "", "", "" } | { 142352, 2342, 34534, 2344, 12346, 7589, 79872, 973453, 96233, 34567 } | { 12432, 2345, 3678, 456, 345, 457, 56758, 4564, 774, 34567 } |
| Returns: 1269258.9999999998 | |
|