Problem Statement |
| | A bunch of people in a large park area are setting up a telephone network using receivers directly connected by wires. There is a lot of spare wire, so the connections need not be straight. The only restriction on the medium is that there be no crossings, since they could cause interference. In other words, if observed from a helicopter above the park, none of the wires can appear to be crossing over one another. Initially, the group of people set up a base network where person 0 is connected to person 1, person 1 is connected to person 2, ..., person i is connected to person i+1, ..., and the last person is connected back to person 0 forming a cycle. Afterwards many other connections were built. The problem is, some of the new connections may have forced crossings to occur.
Given the additional connections that were formed, your method will determine the minimum number of connections that need be removed such that there will not be any crossings. Note that, given a particular set of connections, if it is possible to lay the wires such that they will not cross, the people will do so. This means the people may change their locations and how much wire they use in order to remove crossings. They will not succeed if a crossing is inevitable. Also, since the base network must not be damaged, the removed connections cannot include any of the base network connections.
You will be given 2 int[]s connect1 and connect2 representing the additional connections formed. If the kth elements of connect1 and connect2 are a and b respectively, person a and person b have formed a connection. Note, connections are symmetric, so if a and b are connected then b and a are connected. You will also be given an int numPeople representing the number of people forming the network. Each element of connect1 and connect2 will be integers between 0 and numPeople-1 inclusive. |
| |
Definition |
| | | Class: | TelephoneGame | | Method: | howMany | | Parameters: | int[], int[], int | | Returns: | int | | Method signature: | int howMany(int[] connect1, int[] connect2, int numPeople) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Without loss of generality, you can assume that the people are arranged in a circular pattern. Continuing this image, the base network would be seen from a helicopter as a circle. |
| |
Constraints |
| - | connect1 must contain between 1 and 18 elements inclusive |
| - | connect1 must contain the same number of elements as connect2 |
| - | numPeople must be between 4 and 10000 inclusive |
| - | Element i of connect1 will not be equal to element i of connect2 |
| - | Each element of connect1 and connect2 will be between 0 and numPeople-1 inclusive |
| - | There will be no repeated connections. In other words, if a connection from a to b exists, there will be no other connections of the form a to b or b to a allowed as input. This includes the original connections, so there will be no connections from i to i+1, or from 0 to the last person. |
| |
Examples |
| 0) | |
| | | Returns: 0 | The given connections can easily be formed without crossings as depicted below:
_______
/ |
0---1 /
| /| /
| / | /
|/ |/
3---2
|
|
|
| 1) | |
| | {4,4,4,5,5,6} | {6,7,8,7,8,8} | 10 |
| Returns: 1 | | There is no way for all of these connections to be added without a crossing. |
|
|
| 2) | |
| | |
| 3) | |
| | {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18} | {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19,20} | 100 |
| Returns: 0 | |
|
| 4) | |
| | {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17} | {30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47} | 1000 |
| Returns: 16 | |
|