TwoPolarStations
TCO21 Round 2A · 2021-04-13 · by misof
Problem Statement
A polar station consists of N sensors and two habitats for the researchers. The sensors measure various things: temperature, air pressure, the number of polar bears in vicinity, and so on. All N sensors are placed on the same circle around the habitats. The sensors are numbered from 0 to N-1 in the order in which they lie on the circle. For convenience, the habitats will get the numbers N and N+1.
Yesterday there were 2*N + 1 paths:
- N paths around the circle, each connecting one pair of cyclically adjacent sensors (i.e., one path connects sensors 0 and N-1 and each of the others connects sensors i and i+1 for some i)
- for each sensor a path from the sensor to exactly one of the habitats
- and finally, one path between the two habitats
Habitat N was connected to sensors with numbers between lo and hi, inclusive. Habitat N+1 was connected to all other sensors.
Last night, a blizzard covered all paths with fresh snow. The scientists at the station would like to be able to reach each other and all the sensors again. Thus, they need to pick up shovels and clean some of the paths. But, as you might expect, the scientists are not fond of manual labor and thus they are only willing to clean as few paths as possible (which is clearly always exactly N+1 paths).
Count the number of ways in which the scientists can shovel away the snow. Two ways are different if the sets of cleaned paths differ. Return the count modulo 10^9 + 7.
Notes
- You may only restore a subset of the original paths, you are not able to make new paths where there was no path before the snowfall.
Constraints
- N will be between 3 and 10^9, inclusive.
- 0 <= lo <= hi <= N-1.
3 0 2 Returns: 16
Sensors have numbers 0, 1, 2, habitats have numbers 3 and 4. As there is no other path from habitat 4, the scientists must clear the path between the two habitats. Then they have 16 options which three of the remaining paths they should clear. For example, they may clear the three paths from habitat 3 to the sensors. Another valid solution is to clear the paths 3-0, 0-1, and 0-2. Yet another valid solution is to clear the paths 3-0, 0-1, and 1-2. Cleaning the three paths between sensors does not work, as then you cannot get from the habitats to the sensors. Cleaning the paths 3-0, 3-1, and 0-1 does not work, as there is no way to reach sensor 2 from anywhere.
3 1 1 Returns: 24
Here habitat 3 was connected to sensor 1, while habitat 4 was connected to sensors 0 and 2.
10 1 4 Returns: 28325
4 0 3 Returns: 45
4 3 3 Returns: 69
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 TwoPolarStations with a public method int count(int N, int lo, int hi) · 66 test cases · 2 s / 256 MB per case