RaftingOnDunajec
SRM 813 · 2021-09-15 · by misof
Problem Statement
Time limit is 4 seconds.
Dunajec is a moderately wild river. Around the border between Slovakia and Poland, one popular tourist attraction is rafting on the river.
There are S sights along the river. The sights are in mutually distinct locations.
There are C different companies. Each company offers one raft excursion. Each excursion starts and ends somewhere along the river (at locations different from all the sights).
Each excursion takes the tourists along some non-empty contiguous segment of sights. Each sight can be seen from some non-empty subset of excursions (possibly all of them).
A schedule is a sequence in which we list, for each company, the set of sights visited by their excursion. Two schedules are considered distinct if there is some company that offers a different set of sights in each of them.
(All companies are distinguishable, so if two companies have different excursions and swap them, the new schedule is different from the previous schedule.)
Return the number of valid schedules, modulo 10^9 + 7.
Constraints
- S will be between 1 and 100, inclusive.
- C will be between 1 and 100, inclusive.
7 1 Returns: 1
Seven sights, a single company. As each sight must be on some excursion, the only option is that the company offers an excursion along all the sights.
2 2 Returns: 7
Two sights, two companies. There are: one schedule such that both excursions contain both sights two schedules such that each excursion contains a different one of the two sights four schedules such that one company shows both sights and the other only one of the sights (In the last category we have two ways to choose the company with the longer excursion, and then two ways to choose which sight is shown during the shorter excursion.)
1 7 Returns: 1
As there is only one sight and each company must show some sight on its excursion, we again have just a single valid schedule.
100 100 Returns: 813449009
99 99 Returns: 632648885
2 20 Returns: 486784378
Remember to use the proper modular arithmetic when calculating the answer.
Submissions are judged against all 64 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RaftingOnDunajec with a public method int count(int S, int C) · 64 test cases · 2 s / 256 MB per case