Statistics

Problem Statement for "EventOrder"

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:

  1. Event A starts.
  2. Event B starts.
  3. Event B ends and at the same time event C happens.
  4. Event A ends.

You are given an int longEvents and an int instantEvents. Let X be the total number of distinct schedules with exactly longEvents long and instantEvents instant events. Your method should return the value (X modulo 1,000,000,009).

Definition

Class:
EventOrder
Method:
getCount
Parameters:
int, int
Returns:
int
Method signature:
int getCount(int longEvents, int instantEvents)
(be sure your method is public)

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.

Examples

  1. 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".

  2. 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".

  3. 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.

  4. 0

    4

    Returns: 75

  5. 1000

    1000

    Returns: 665489683

  6. 1

    0

    Returns: 1

  7. 0

    1

    Returns: 1

  8. 2

    1

    Returns: 101

  9. 1

    2

    Returns: 31

  10. 3

    0

    Returns: 409

  11. 0

    3

    Returns: 13

  12. 4

    1

    Returns: 323093

  13. 4

    7

    Returns: 13989478

  14. 7

    4

    Returns: 417933133

  15. 997

    998

    Returns: 359149531

  16. 998

    997

    Returns: 605235182

  17. 857

    789

    Returns: 726313412

  18. 997

    1

    Returns: 529082900

  19. 2

    355

    Returns: 889723939

  20. 254

    245

    Returns: 229655616

  21. 936

    909

    Returns: 702935821

  22. 987

    988

    Returns: 129627381

  23. 956

    435

    Returns: 664968911

  24. 234

    986

    Returns: 390337642

  25. 356

    356

    Returns: 98103717

  26. 1000

    0

    Returns: 374847625

  27. 0

    1000

    Returns: 629517728

  28. 1000

    1

    Returns: 656944515

  29. 1

    1000

    Returns: 862202137

  30. 474

    747

    Returns: 125016932

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: