CommitteeContinuity
TCO22 Wildcard · 2022-04-14 · by misof
Problem Statement
Time limit: 5 seconds.
A country club has M members. They are numbered from 0 to M-1.
The club has existed for Y years. The years are numbered from 0 to Y-1. All M members were in the club during its entire existence.
At the start of each year the club elected a steering committee for that year from among its members. There were no restrictions on the size of the committee, so it's possible that in different years the committee had a different number of members. It's even possible that for some years everyone was on the steering committee.
There was only one rule that was dilligently followed during the club's existence: due to continuity, the new committee and the old committee from previous year may never be disjoint. There must always be at least one person who stays on the committee (to take care of projects that are still ongoing).
Most of the information about the past steering committes has been lost when the club's library burned down. We only remember some (potentially incomplete) information about a very small number of members.
This information is given in the
A valid history is a sequence of Y steering committees that is consistent with the continuity rule and all the remembered information.
Count all valid histories. Return that count modulo 10^9 + 7.
Constraints
- M will be between 1 and 50, inclusive.
- Y will be between 1 and 50, inclusive.
- year will have between 0 and 50 elements, inclusive.
- Each element of year will be between 0 and Y-1, inclusive.
- member will have the same number of elements as year.
- Each element of member will be between 0 and M-1, inclusive.
- All pairs (year[i], member[i]) will be mutually distinct.
- member will contain at most 10 distinct values.
3
5
{0, 1, 2, 3, 4}
{0, 0, 0, 0, 0}
Returns: 1024
We are told that member #0 was on the committee during all five years. As this takes care of continuity, there are no other constraints on the committee's composition. Thus, during each of the five years the committee had four options: it was {0}, {0, 1}, {0, 2}, or {0, 1, 2}. As these choices are mutually independent, there are 4^5 = 1024 valid histories.
2
3
{}
{}
Returns: 17
Two members, three years. All 17 valid histories are listed below: {0}, {0}, {0} {0}, {0}, {0, 1} {0}, {0, 1}, {0} {0}, {0, 1}, {0, 1} {0}, {0, 1}, {1} {0, 1}, {0}, {0} {0, 1}, {0}, {0, 1} {0, 1}, {0, 1}, {0} {0, 1}, {0, 1}, {0, 1} {0, 1}, {0, 1}, {1} {0, 1}, {1}, {0, 1} {0, 1}, {1}, {1} {1}, {0, 1}, {0} {1}, {0, 1}, {0, 1} {1}, {0, 1}, {1} {1}, {1}, {0, 1} {1}, {1}, {1}
2
3
{1, 1}
{0, 1}
Returns: 9
Again, two people and three years. This time we are told that during year 1 the steering committee contained both 0 and 1, which means that it must have been {0, 1}. Each valid history now has the following form: (any non-empty committee), {0, 1}, (any non-empty committee). Thus, there are 3*3 = 9 valid histories.
40
1
{}
{}
Returns: 511620082
Obviously, this return value is (2^40 - 1) modulo (10^9 + 7).
4
5
{1, 2}
{1, 2}
Returns: 111156
Submissions are judged against all 66 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CommitteeContinuity with a public method int count(int M, int Y, vector<int> year, vector<int> member) · 66 test cases · 2 s / 256 MB per case