NoteTakers
SRM 850 · 2023-10-25 · by misof
Problem Statement
The university campus has N buildings, numbered from 0 to N-1.
In order to move between buildings the students can use walkways. For each valid index i, there is a walkway that connects buildings X[i] and Y[i], and it takes D[i] seconds to use it (in either direction). It is possible that some pairs of buildings are connected by multiple direct walkways, and it is also possible that some buildings are unreachable from others.
There will be some lectures in these buildings. For each valid index j, the lecture number j is happening in building B[j] during the open interval of times starting at T1[j] and ending at T2[j].
A student can only take notes on a lecture if they are attending it from start to end without interruptions. If there are multiple lectures at the same time in the same building, each takes (naturally) place in a different lecture room and so it is not possible to attend multiple lectures at the same time: in such cases each student must choose one of the lectures.
A group of students does not want to attend lectures but they do want to have notes from all the lectures that will be given on campus. They have decided to draw straws. Only the unlucky losers will be sent to attend lectures and take notes.
Each note-taker can start at time 0 in a building of their choice. Then they can attend lectures to take notes, and between those lectures they can use walkways to move between buildings in any way they like.
Help the students by finding the smallest possible number of note-takers and producing one schedule that tells them who should attend which lectures in which order.
Return a
Notes
- Any valid solution will be accepted.
- Your only goal is to minimize the total number of note-takers. Their schedules do not have to be "balanced" in any way.
Constraints
- N will be between 1 and 100, inclusive.
- X will contain between 0 and 250 elements, inclusive.
- Y and D will contain the same number of elements as X.
- Each element of X will be between 0 and N-1, inclusive.
- Each element of Y will be between 0 and N-1, inclusive.
- Each element of D will be between 1 and 10^9, inclusive.
- B will contain between 1 and 300 elements, inclusive.
- T1 and T2 will contain the same number of elements as B.
- Each element of B will be between 0 and N-1, inclusive.
- Each element of T1 will be between 0 and 10^9, inclusive.
- Each element of T2 will be between 0 and 10^9, inclusive.
- For each j, T1[j] will be less than T2[j].
1
{}
{}
{}
{0, 0, 0}
{10, 11, 12}
{20, 21, 22}
Returns: {0, -1, 1, -1, 2, -1 }
One building, no walkways, three lectures. As each pair of lectures overlaps, we clearly need (at least) three note-takers.
2
{0, 1}
{0, 0}
{7, 10}
{0, 0, 1}
{20, 30, 0}
{30, 47, 10}
Returns: {2, 0, 1, -1 }
Two buildings, two walkways: a loop from 0 to 0 that takes 7 seconds, and a path between 1 and 0 that takes 10 seconds. Three lectures. It is possible (but only just) for a single person to catch all three. Note that in this problem moving to another lecture room in the same building can be done instantly, and so at time=30 when lecture 0 ends the note-taker can instantly move to lecture 1 that is about to start in the same building.
4
{0, 1, 2}
{1, 2, 3}
{10, 10, 10}
{0, 0, 1, 1, 2, 2, 3, 3}
{4, 7, 33, 26, 47, 125, 132, 54}
{14, 22, 34, 34, 122, 256, 247, 113}
Returns: {0, 3, 7, 5, -1, 1, 2, 4, 6, -1 }
This campus has buildings along a line. Two note-takers are enough to obtain the notes from all planned lectures. According to the sample output, one note-taker can visit lectures 0, 3, 7, 5 in this order while the other one visits 1, 2, 4, 6.
1
{}
{}
{}
{0, 0, 0}
{0, 10, 10}
{10, 20, 30}
Returns: {0, 1, -1, 0, 2, -1 }
In our returned solution both note-takers attend lecture 0. This is still a valid solution: each lecture was visited by at least one note-taker, so we have all the lecture notes we need.
10
{4}
{7}
{47}
{4, 5}
{500, 999999999}
{501, 1000000000}
Returns: {0, -1, 1, -1 }
As there is no way to reach building 5 from building 4, we need two different note-takers. (One can start at time=0 in either of buildings 4 and 7 and eventually catch lecture 0 in building 4, the other must start exactly in building 5 and remain there until lecture 1 takes place.)
Submissions are judged against all 131 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NoteTakers with a public method vector<int> solve(int N, vector<int> X, vector<int> Y, vector<int> D, vector<int> B, vector<int> T1, vector<int> T2) · 131 test cases · 2 s / 256 MB per case