Problem Statement |
| | You are the king of Nowhere Land. You've recently received some big donations, so you've decided to hire more guards to protect your country. There are k different guarding companies in Nowhere Land. Each guarding company has agencies in various cities. If a guarding company has an agency in a city, then that company is allowed to have at most one guard working in that city. Otherwise, the company is not allowed to have any guards in that city. As long as you obey this rule, you can add as many new guards as you want. However, you cannot fire or move existing guards.
There's one problem though. Some pairs of cities cooperate with each other and have certain requirements when hiring guards. If city A cooperates with city B, and a certain company has a guard working in city A but not city B, that is considered a conflict. For each pair of cooperating cities, each distinct company that breaks this rule counts as a conflict, so there may be multiple conflicts within a single pair of cities.
You are given a String[] cities. The number of elements in cities is equal to the number of cities in Nowhere Land. The j-th character of the i-th element of cities is '1' (one) if cities i and j cooperate, and '0' (zero) otherwise. You are also given String[]s guards and agencies. The i-th element of guards is a space separated list of guarding companies that already have guards working in city i. The i-th element of agencies is a space separated list of guarding companies that have an agency in city i. Each guarding company is represented as an integer between 0 and k-1, inclusive. Return the minimum possible number of conflicts that can exist after hiring additional guards. |
| |
Definition |
| | | Class: | NowhereLand | | Method: | placeGuards | | Parameters: | String[], int, String[], String[] | | Returns: | int | | Method signature: | int placeGuards(String[] cities, int k, String[] guards, String[] agencies) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | cities will contain between 1 and 50 elements, inclusive. |
| - | The number of characters in each element of cities will be equal to the number of elements in cities. |
| - | Each character of each element of cities will be a zero ('0') or a one ('1'). |
| - | The i-th character of i-th element of cities will be '0'. |
| - | The i-th character of j-th element of cities will be the same as the j-th character of i-th element. |
| - | k will be between 1 and 50, inclusive. |
| - | cities, guards and agencies will all contain the same number of elements. |
| - | Each element of guards will contain between 0 and 50 characters, inclusive. |
| - | Each element of guards will be a single space separated list of distinct integers between 0 and k - 1, inclusive, with no extra leading zeroes, without leading or trailing spaces. |
| - | Each element of agencies will contain between 0 and 50 characters, inclusive. |
| - | Each element of agencies will be a single space separated list of distinct integers between 0 and k - 1, inclusive, with no extra leading zeroes, without leading or trailing spaces. |
| - | For each integer in the i-th element of guards, this integer will also be in the i-th element of agencies. |
| |
Examples |
| 0) | |
| | { "0111",
"1000",
"1000",
"1000" } | 1 | { "0", "", "", "" } | { "0", "0", "", "0" } |
| Returns: 1 | | There's only one guarding company in Nowhere Land. You can hire additional guards in cities 1 and 3. The best solution is to hire guards in both these cities. Then there will be just one conflict (between cities 0 and 2). |
|
|
| 1) | |
| | { "011",
"101",
"110" } | 1 | { "0", "", "" } | { "0", "", "" } |
| Returns: 2 | | You can't hire additional guards here. There are 2 conflicts (between cities 0 and 1 and cities 0 and 2). |
|
|
| 2) | |
| | { "011",
"101",
"110" } | 1 | { "", "", "" } | { "0", "0", "0" } |
| Returns: 0 | | There are two possible solutions. You can hire a guard in each of the three cities and get rid of all conflicts. Alternatively, don't hire anybody and there will also be no conflicts. |
|
|
| 3) | |
| | { "010100",
"101100",
"010011",
"110010",
"001100",
"001000" } | 3 | { "1 2", "", "1", "", "0", "0" } | { "0 1 2", "0 1", "0 1 2", "1 2", "0", "0" } |
| Returns: 7 | | In this example there are 3 guarding companies. A possible solution is to hire a guard from company 0 in city 2 and guards from company 1 in cities 1 and 3. As a result, there will be 7 conflicts: two between cities 3 and 4 and one between cities 0 and 1, 0 and 3, 1 and 2, 2 and 4, 2 and 5. |
|
|