Statistics

Problem Statement for "RaceOrdering"

Problem Statement

You are trying to predict the outcome of a race between n runners, numbered from 0 to n - 1.You are given two int[]s, first and second. It is guaranteed that for all i, the runner numbered first[i] will always beat the runner numbered second[i]. Determine how many final orderings are possible, modulo 1,000,003. If the information is contradictionary, return 0. Runners are never tied.

Definition

Class:
RaceOrdering
Method:
countOrders
Parameters:
int, int[], int[]
Returns:
int
Method signature:
int countOrders(int n, int[] first, int[] second)
(be sure your method is public)

Constraints

  • n will be between 1 and 30, inclusive.
  • first and second will each contain between 0 and 15 elements, inclusive.
  • first and second will contain the same number of elements.
  • Each element of first and second will be between 0 and n - 1, inclusive.
  • first[i] does not equal second[i] for all i between 0 and m - 1, inclusive, where m is the number of elements in first and second.

Examples

  1. 3

    {1}

    {2}

    Returns: 3

    Contestant 1 beat contestant 2, so the valid orders are 012, 102 and 120.

  2. 4

    {0, 0}

    {1, 2}

    Returns: 8

    Contestant 0 beat contestants 1 and 2, but there is no information on contestant 3. The valid orderings are 3012, 3021, 0312, 0321, 0132, 0231, 0123 and 0213.

  3. 10

    {1, 2, 3}

    {2, 3, 1}

    Returns: 0

    There is no way to satisfy this cycle.

  4. 30

    {}

    {}

    Returns: 90317

  5. 2

    {0}

    {1}

    Returns: 1

  6. 3

    {0, 1}

    {1, 2}

    Returns: 1

  7. 2

    {0, 1}

    {1, 0}

    Returns: 0

  8. 3

    {0, 1, 0}

    {1, 2, 2}

    Returns: 1

  9. 30

    {}

    {}

    Returns: 90317

  10. 30

    {0}

    {9}

    Returns: 545160

  11. 1

    {}

    {}

    Returns: 1

  12. 10

    {0, 1, 3, 4, 6, 7, 0, 3, 1, 4, 2, 5}

    {1, 2, 4, 5, 7, 8, 3, 6, 4, 7, 5, 8}

    Returns: 420

  13. 30

    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28}

    {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}

    Returns: 439976

  14. 16

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

    Returns: 1

  15. 30

    {29, 25, 21, 17, 13, 9, 5, 28, 24, 20, 16, 12, 8, 4, 1}

    {27, 23, 19, 15, 11, 7, 3, 26, 22, 18, 14, 10, 6, 2, 0}

    Returns: 439976

  16. 15

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0}

    Returns: 0

  17. 15

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 9}

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 4}

    Returns: 0

  18. 8

    {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2}

    {3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7}

    Returns: 768

  19. 17

    {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7}

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 2}

    Returns: 20144

  20. 17

    {0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7}

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0}

    Returns: 0

  21. 27

    {0, 0, 3, 3, 6, 6, 9, 9, 12, 12, 15, 15, 18, 18, 20}

    {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 24}

    Returns: 390723

  22. 30

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

    Returns: 68145

  23. 30

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    Returns: 68145

  24. 30

    {1, 2, 3, 4, 5, 6, 7, 9, 9, 9, 9, 9, 9, 9, 9}

    {0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 0}

    Returns: 681812

  25. 6

    {0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4}

    {1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5}

    Returns: 1

  26. 15

    {0, 9, 2, 1, 0, 2, 1, 9}

    {1, 4, 5, 6, 1, 5, 6, 4}

    Returns: 268542

  27. 30

    {22, 4, 17, 1, 27, 24, 10, 10, 4, 20, 10, 22, 0, 0, 17}

    {1, 24, 3, 15, 20, 18, 20, 5, 15, 1, 24, 0, 5, 4, 15}

    Returns: 779866

  28. 29

    {17, 24, 13, 13, 13, 27, 18, 24, 21, 27, 17, 11, 27, 24, 18}

    {7, 18, 18, 10, 11, 10, 10, 27, 23, 10, 10, 23, 23, 10, 11}

    Returns: 487245

  29. 10

    {5, 9, 5, 2, 8, 2, 9, 9, 2, 9, 8, 5, 9, 2, 5}

    {3, 2, 3, 3, 5, 3, 5, 5, 5, 2, 3, 3, 5, 3, 3}

    Returns: 90720

  30. 30

    {24, 10, 11, 14, 9, 7, 17, 10, 11, 2, 11, 14, 11, 5, 4}

    {22, 12, 0, 18, 0, 18, 8, 28, 28, 0, 26, 24, 8, 18, 12}

    Returns: 110128

  31. 28

    {20, 8, 24, 10, 21, 2, 10, 17, 24, 24, 8, 15, 24, 17}

    {7, 2, 0, 20, 16, 16, 24, 24, 25, 16, 14, 16, 2, 13}

    Returns: 175276

  32. 30

    {0, 4, 15, 15, 10, 26, 7, 29, 28, 17, 9, 7, 8, 8, 4}

    {5, 0, 27, 21, 0, 17, 24, 9, 29, 12, 5, 12, 24, 13, 7}

    Returns: 65712

  33. 30

    {0, 4, 15, 15, 10, 26, 7, 29, 28, 17, 9, 7, 8, 8, 4}

    {5, 0, 27, 21, 0, 17, 24, 9, 29, 12, 5, 12, 24, 13, 7}

    Returns: 65712

  34. 30

    {0, 0, 1, 25, 2, 3, 0, 0, 2, 5, 6, 7, 7, 9, 10 }

    {1, 1, 25, 4, 3, 4, 3, 2, 25, 6, 9, 6, 8, 10, 11 }

    Returns: 71776

  35. 30

    {0, 0, 3, 3, 6, 6, 9, 9, 12, 12, 15, 15, 18, 18, 21 }

    {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22 }

    Returns: 644970

  36. 30

    {1, 2, 3, 3, 4, 5, 1, 3, 12, 14, 16, 12, 18, 18, 22 }

    {2, 3, 4, 5, 6, 6, 6, 5, 13, 15, 17, 17, 19, 6, 1 }

    Returns: 701220

  37. 30

    {20, 7, 1, 6, 15, 6, 29, 4, 10, 19, 20, 17, 10, 0, 28 }

    {6, 17, 4, 14, 16, 19, 7, 17, 6, 17, 4, 14, 4, 19, 7 }

    Returns: 611149

  38. 30

    {0, 20, 20, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }

    {20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 15, 16, 17, 18, 19 }

    Returns: 959986

  39. 30

    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 20, 24, 19, 28 }

    {1, 3, 5, 7, 9, 11, 13, 15, 19, 19, 21, 23, 25, 27, 29 }

    Returns: 946647

  40. 30

    {1, 2, 3, 5, 6, 6, 6, 18, 19, 20, 20, 20, 20, 24, 25 }

    {5, 5, 5, 6, 7, 9, 19, 19, 23, 1, 21, 23, 24, 25, 26 }

    Returns: 953931

  41. 30

    {1, 1, 2, 2, 3, 3, 5, 5, 4, 4, 6, 6, 7, 7, 9 }

    {2, 3, 4, 5, 4, 6, 7, 8, 8, 9, 9, 10, 11, 12, 12 }

    Returns: 818649

  42. 30

    {11, 2, 7, 15, 22, 3, 1, 20, 3, 17, 2, 17, 19, 2, 3 }

    {1, 5, 3, 3, 23, 29, 13, 25, 5, 1, 6, 3, 1, 3, 1 }

    Returns: 132019

  43. 30

    {3, 4, 5, 6, 7, 8, 9, 10, 20, 20, 20, 20, 27, 27, 28 }

    {20, 20, 20, 20, 27, 20, 20, 20, 11, 12, 13, 14, 15, 20, 29 }

    Returns: 717966

  44. 30

    {0, 0 }

    {1, 1 }

    Returns: 545160

  45. 27

    {1, 1, 3, 4, 5, 7, 7, 9, 10, 6, 13 }

    {2, 5, 2, 3, 3, 6, 8, 8, 9, 10, 14 }

    Returns: 829866

  46. 30

    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 }

    {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 }

    Returns: 439976

  47. 30

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }

    {15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 }

    Returns: 439976

  48. 12

    {0, 0, 0, 3, 3, 8, 9, 5, 6, 10 }

    {1, 2, 3, 2, 4, 5, 5, 7, 7, 11 }

    Returns: 64445

  49. 30

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 }

    {8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14 }

    Returns: 88202

  50. 30

    {0, 0, 4, 4, 8, 8, 12, 12, 16, 16, 20, 20, 24, 24 }

    {1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22, 25, 26 }

    Returns: 289937

  51. 30

    {11, 12, 13, 14, 15, 16, 17, 21, 22, 23, 24, 25, 26, 27, 28 }

    {10, 10, 10, 10, 10, 10, 10, 20, 20, 20, 20, 20, 20, 20, 20 }

    Returns: 681812

  52. 30

    {0, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15 }

    {1, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 }

    Returns: 36344

  53. 30

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 68145

  54. 3

    {0, 1 }

    {2, 2 }

    Returns: 2

  55. 30

    {1, 4, 6, 2, 9, 12, 10 }

    {8, 2, 29, 7, 6, 11, 6 }

    Returns: 170453

  56. 30

    {0, 1, 2, 3, 4, 5, 20, 20, 24, 25 }

    {1, 6, 8, 9, 11, 11, 21, 23, 26, 26 }

    Returns: 853537

  57. 30

    {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 }

    {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 }

    Returns: 439976

  58. 24

    {1, 1, 4, 5, 7, 8, 9 }

    {2, 3, 1, 1, 8, 9, 10 }

    Returns: 581259

  59. 9

    {0, 1, 2, 3, 3, 4, 4, 4 }

    {2, 2, 3, 4, 4, 5, 5, 5 }

    Returns: 1008

  60. 30

    {0, 0, 0, 1, 1, 2, 5, 5, 10, 12, 14, 16, 18, 20, 22 }

    {1, 1, 2, 3, 4, 4, 1, 3, 11, 13, 15, 17, 19, 21, 23 }

    Returns: 343893

  61. 30

    {1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0, 0, 0, 0, 0 }

    {0, 0, 0, 0, 0, 0, 0, 0, 11, 12, 13, 14, 15, 16, 17 }

    Returns: 102575

  62. 30

    {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 6, 7, 8, 9, 25 }

    {1, 2, 3, 4, 5, 6, 7, 3, 5, 7, 10, 10, 10, 10, 26 }

    Returns: 734408

  63. 2

    {1 }

    {0 }

    Returns: 1

  64. 30

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

    {16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 0 }

    Returns: 439976

  65. 30

    {5, 4, 4, 1, 0, 3, 2, 8 }

    {4, 6, 0, 0, 2, 2, 7, 7 }

    Returns: 321131

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: