EventOrder
TCO11 Wildcard Round · 2011-05-07 · by misof
Problem Statement
We are given a set of events. Each of the events is unique. Some events are long, each of these may take any positive amount of time. Different long events may take different amounts of time. The other events are instant, each of these happens instantly at some moment in time.
We want to arrange the events into a schedule. We do not care about exact times when the events take place, we only consider their relative order. For example, given long events A and B and an instant event C, one of the possible schedules looks as follows:
- Event A starts.
- Event B starts.
- Event B ends and at the same time event C happens.
- Event A ends.
You are given an
Constraints
- longEvents will be between 0 and 1000, inclusive.
- instantEvents will be between 0 and 1000, inclusive.
- At least one of longEvents and instantEvents will be positive.
0 2 Returns: 3
If we label the events A and B, then the three schedules are "A before B", "both at the same time", and "A after B".
1 1 Returns: 5
If we label the long event A and the instant event B, then the five schedules are "B before A starts", "B when A starts", "B during A", "B when A ends", and "B after A".
2 0 Returns: 13
There are 6 schedules in which no two endpoints of events coincide, 2 schedules when one event starts when the other one ends, 2 schedules with the same beginning and different end, 2 with same end and different beginning, and 1 when the events start and end at the same time.
0 4 Returns: 75
1000 1000 Returns: 665489683
Submissions are judged against all 30 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EventOrder with a public method int getCount(int longEvents, int instantEvents) · 30 test cases · 2 s / 256 MB per case