RabbitAndTable
2017 TCO Final · 2017-03-31 · by cgy4ever
2017 TCO Final · 2017-03-31 · by cgy4ever · Dynamic Programming
Problem Statement
Problem Statement
A group of n rabbits is about to have dinner.
For the dinner, they will sit around one or more round tables.
They now need to divide themselves into groups that will each share one table.
You know that rabbits are shy. More precisely, you are given theint[] x with n elements.
For each valid i, rabbit i wants to sit at a table that has x[i] or fewer rabbits (including rabbit i itself).
Two ways of dividing rabbits into groups are considered different if there is a pair of rabbits that are in the same group in one way and in two different groups in the other way.
Let Z be the number of ways to divide rabbits into groups while respecting all their wishes. Compute and return the value Z modulo (10^9 + 7).
You know that rabbits are shy. More precisely, you are given the
Two ways of dividing rabbits into groups are considered different if there is a pair of rabbits that are in the same group in one way and in two different groups in the other way.
Let Z be the number of ways to divide rabbits into groups while respecting all their wishes. Compute and return the value Z modulo (10^9 + 7).
Constraints
- n will be between 2 and 2,000, inclusive.
- x will contain exactly n elements.
- Each element in x will be between 1 and n, inclusive.
Examples
0)
{3,3,3}
Returns: 5
All rabbits are ok with any number of rabbits in their group, so we have 5 solutions: {0}, {1}, {2} {0, 1}, {2} {0}, {1, 2} {0, 2}, {1} {0, 1, 2}
1)
{3,2,3}
Returns: 4
This time one of the rabbits does not want to be in a group of size 3. So this time we only have 4 valid ways to form the groups: {0}, {1}, {2} {0, 1}, {2} {0}, {1, 2} {0, 2}, {1}
2)
{1,1,1,1,1,1,1,1,1,1}
Returns: 1
All rabbits are very shy and can only be alone.
3)
{15,15,15,15,15,15,15,15,15,15,15,15,15,15,15}
Returns: 382958538
The answer is 1382958545 % (10^9+7).
4)
{3,2,2,1,5,4,4,1,2}
Returns: 272
Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RabbitAndTable with a public method int count(vector<int> x) · 113 test cases · 2 s / 256 MB per case