Connection Status:
Competition Arena > Visitors

Visitors

TCC India 2018 Final · 2018-06-29 · by misof

TCC India 2018 Final · 2018-06-29 · by misof · Dynamic Programming
Class Name: Visitors
Return Type: int
Method Name: countSchedules
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Patrik runs a local game store. Recently, a flood damaged their records and he is now trying to reconstruct them from pieces of information he recovered.

You are given all the information Patrik has: a int[] visitors. For each i, visitors[i] is the number of unique people who took part in exactly i events that occurred in the store this year. The events occurred sequentially with no overlaps. Each event had one or more participants. Note that Patrik doesn't know the actual number of events that occurred.

Two schedules are different if they have a different number of events. Two schedules are also different if they have the same number of events, but for some i the i-th event (in chronological order) in the first schedule and the i-th event in the second schedule have a different set of participants.

Count all valid schedules and return their count modulo (10^9 + 7).

Constraints

  • visitors will contain between 2 and 50 elements, inclusive.
  • Each element of visitors will be between 0 and 50, inclusive.
  • visitors[0] will be 0.
  • The sum of visitors will be positive.
  • The sum of i * visitors[i] will not exceed 3000.
Examples
0)
{0,1}
Returns: 1

There was a single person and they visited the store once. There is only one valid schedule: there was one event and the person took part in that event.

1)
{0,0,0,1}
Returns: 1

Again, there is only one valid schedule: there were three events and the only visitor attended each of them.

2)
{0,3}
Returns: 13

There were three people (A, B, C) who attended one event each. One valid schedule is that A attended event 1, then C attended event 2, and then B attended event 3. Another valid schedule is that B attended event 1, A attended event 2, and C attended event 3. Yet another valid schedule: A and C attended event 1 and then B attended event 2.

3)
{0,1,1}
Returns: 5

Note that the schedule in which A attends event 1 and then B attends events 2 and 3 is different from the schedule in which B attends event 1, then A attends event 2, and then B attends event 3.

4)
{0,1,2,3,4}
Returns: 119998118

Don't forget to use the modular arithmetic.

Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Visitors with a public method int countSchedules(vector<int> visitors) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous