FamilySeatingArrangement
TCO19 Round 3A · 2019-04-15 · by lg5293
Problem Statement
Several families are at a birthday party.
Each family consists of exactly one parent and some children.
You are given the
There are k large tables at the party. Everyone at the party is now supposed to sit down at one of the tables. Each individual table can fit an unlimited number of people. The only constraint is that it is forbidden for any child to sit at a table with a different parent unless their own parent is also sitting at that table.
Count all ways in which the people can sit down, and return that count modulo 10^9 + 7.
Two ways are different if there is some person who is sitting at a different table. All people and tables are distinguishable from each other. Some tables may remain empty. The order in which people sit at the table does not matter.
Constraints
- a will have between 1 and 1,000 elements, inclusive.
- Each element of a will be between 1 and 1,000, inclusive.
- k will be between 1 and 1,000, inclusive.
{2,1}
2
Returns: 18
There are two families: a parent with 2 children and a parent with 1 child. Let A be the parent of the first family and a1,a2 be the children, and let B be the parent of the second family, and b1 be the only child. There are 18 ways to seat these families at k = 2 tables. The first 9 ways are listed below. In the other 9 ways the tables are swapped. {A, a1, a2, B, b1}, {} {A, a2, B, b1}, {a1} {A, a1, B, b1}, {a2} {A, B, b1}, {a1, a2} {A, a1, a2, B}, {b1} {A, a2, B}, {a1, b1} {A, a1, B}, {a2, b1} {A, B}, {a1, a2, b1} {A, a1, a2} {B, b1} Note that in the first case, even though a1 is sitting at the same table as B, this is allowed since A is sitting at that table. An example of a bad arrangement is {a1,a2,B,b1}, {A}, since a1 and a2 cannot sit at the same table as B unless A is also present.
{2,1}
3
Returns: 129
{2,1}
1000
Returns: 989021965
{1,1,1,1,1,1,1,1,1,1,1,1}
8
Returns: 604306839
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
211
Returns: 775937801
Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FamilySeatingArrangement with a public method int countWays(vector<int> a, int k) · 62 test cases · 2 s / 256 MB per case