Connection Status:
Competition Arena > RabbitAndTable

RabbitAndTable

2017 TCO Final · 2017-03-31 · by cgy4ever

2017 TCO Final · 2017-03-31 · by cgy4ever · Dynamic Programming
Class Name: RabbitAndTable
Return Type: int
Method Name: count
Arg Types: (vector<int>)
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 the int[] 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).

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.

Statement by TopCoder, Inc. — view the original on the archive.

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

Submitting as anonymous