CentaurCompanyDiv2
SRM 570 · 2012-12-13 · by snuke
Problem Statement
The Centaur company has N servers, numbered 1 through N. These servers are currently connected into a network. The topology of the network is a tree. In other words, there are exactly N-1 bidirectional cables, each connecting some two servers in such a way that the entire network is connected.
The Centaur company is about to split into two new companies: the Human company and the Horse company. When this happens, the companies will divide the servers somehow. Once they divide their servers, they will cut each cable that connects a server of the Horse company and a server of the Human company.
While the Horse company has a lot of cables, the Human company does not have any. Therefore, when dividing the servers, the Human company must get a set of servers that will remain connected after the cables are cut.
You are given two
Compute and return the number of different ways in which the two companies may divide the servers. (It is possible that one of the companies will get no servers at all.)
Notes
- N can be determined as (1 + the length of a).
Constraints
- N will be between 2 and 51, inclusive.
- a and b will contain exactly N-1 elements.
- Each element of a and b will be between 1 and N, inclusive.
- The network defined by a and b will be a tree (as explained in the problem statement).
{1}
{2}
Returns: 4
There are 2^2 = 4 ways to divide the servers between two companies. For any division, the Human company's servers will remain connected.
{2,2}
{1,3}
Returns: 7
There are 2^3 = 8 ways to divide the servers between two companies. However, if the Human company gets server 1 and server 3, and the Horse company gets server 2, the Human company's servers will not be connected. Therefore the number of valid ways is 8 - 1 = 7.
{1,2,3,4,5,6,7,8,9}
{2,3,4,5,6,7,8,9,10}
Returns: 56
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51}
Returns: 1125899906842675
The answer overflows a 32-bit integer data type.
{51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51,51}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
Returns: 1125899906842675
Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CentaurCompanyDiv2 with a public method long long count(vector<int> a, vector<int> b) · 73 test cases · 2 s / 256 MB per case