Statistics

Problem Statement for "TheMoviesLevelThreeDivTwo"

Problem Statement

John and Brus have received a box of new movies to review. There are N movies, numbered 0 to N-1, inclusive, and John and Brus each want to review every movie. John has proposed that they use a special device called a review queue. The device supports two operations: add a movie, and take a movie (if at least one exists in the queue). When taking a movie, the movie in the queue that was added earliest is removed from the queue. John and Brus each have their own review queue.

There are two phases to the review process. In the first phase, John distributes the movies between the two queues. He first takes movie 0 and adds it to either John's queue or Brus's queue, then he takes movie 1 and adds it to one of the queues, and so on, until each movie has been added to one of the queues.

In the second phase, John and Brus simultaneously start reviewing movies. Each of them will continuously repeat the following sequence of moves.
  1. Take a movie from his own review queue. If this move is not successful because his queue is empty, he will quit completely (even if more movies will be added to his queue at a later time).
  2. Review this movie.
  3. Add this movie to the other person's review queue if he has not yet reviewed it.
Steps 1 and 3 take no time. If a queue receives an add and a take operation at the same time, the add operation is completed first. So, for example, if John's queue is empty and Brus attempts to add a movie to John's queue at the same time that John tries to take a movie from the same queue, the movie will get added and John will succeed in taking the movie from the queue.

The amount of time required for step 2 varies between John and Brus for each movie. When reviewing a movie, neither John nor Brus feel that it is always necessary to view the entire movie. It takes John timeJ[i] minutes to review movie i, and it takes Brus timeB[i] minutes.

In the first phase, since John has two choices for distributing each movie, there are 2^N ways to distribute the movies. A distribution is considered good if John and Brus each review every movie during the second phase before quitting. Return the total number of good ways to distribute the movies.

Definition

Class:
TheMoviesLevelThreeDivTwo
Method:
find
Parameters:
int[], int[]
Returns:
int
Method signature:
int find(int[] timeJ, int[] timeB)
(be sure your method is public)

Constraints

  • timeJ will contain between 1 and 20 elements, inclusive.
  • timeJ and timeB will contain the same number of elements.
  • Each element of timeJ will be between 1 and 20, inclusive.
  • Each element of timeB will be between 1 and 20, inclusive.

Examples

  1. {4, 4}

    {4, 4}

    Returns: 2

    We are interested in two distributions where John and Brus get one movie each.

  2. {1, 4}

    {4, 2}

    Returns: 1

    Here the only possible distribution is where Brus gets the first movie and John gets the second one.

  3. {10, 10, 10, 10}

    {1, 1, 1, 10}

    Returns: 3

    Brus must get all the movies except one of the first three during the distribution.

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

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

    Returns: 98

  5. {7, 7}

    {9, 9}

    Returns: 0

  6. {1, 9, 1, 6, 7, 2}

    {4, 4, 9, 3, 1, 3}

    Returns: 38

  7. {3, 5}

    {1, 1}

    Returns: 0

  8. {7}

    {7}

    Returns: 0

  9. {20}

    {20}

    Returns: 0

  10. {1}

    {17}

    Returns: 0

  11. {1, 7, 5, 17, 13, 6, 12, 3}

    {17, 5, 9, 11, 5, 8, 11, 19}

    Returns: 193

  12. {10, 4, 9}

    {5, 17, 10}

    Returns: 3

  13. {15, 17, 17, 5, 1, 9, 5, 9, 13, 11}

    {12, 1, 13, 1, 14, 9, 19, 11, 13, 11}

    Returns: 903

  14. {17, 13, 1, 17, 16, 17, 5, 9, 6, 8, 20, 5, 20, 3, 1, 11, 11, 13, 11}

    {13, 1, 5, 6, 1, 1, 1, 5, 9, 5, 6, 1, 20, 9, 18, 13, 11, 15, 2}

    Returns: 375315

  15. {5}

    {15}

    Returns: 0

  16. {19, 5, 1, 17, 16, 3, 3, 1, 2, 1, 17, 13, 19}

    {5, 17, 9, 19, 20, 11, 14, 19, 3, 5, 9, 16, 1}

    Returns: 6457

  17. {8}

    {9}

    Returns: 0

  18. {15, 5, 16, 11, 7, 14, 10, 6, 5, 13}

    {18, 4, 7, 9, 10, 15, 5, 11, 17, 1}

    Returns: 954

  19. {20, 6, 3, 5, 11, 2, 17, 17, 9, 3, 16, 11, 7, 9, 5, 17, 8}

    {16, 17, 17, 9, 7, 11, 17, 7, 3, 6, 11, 15, 11, 8, 19, 17, 17}

    Returns: 126914

  20. {13, 1, 1, 5}

    {5, 1, 6, 1}

    Returns: 4

  21. {9, 9, 12, 3, 11, 17, 1, 4, 1, 7, 13, 1, 7, 5, 5, 11, 6, 12, 1, 3}

    {15, 14, 5, 19, 14, 11, 9, 4, 13, 5, 5, 7, 13, 8, 9, 11, 8, 11, 17, 1}

    Returns: 957134

  22. {11, 19, 9, 10, 15, 14, 1, 19, 16, 17, 5, 13, 1, 1, 13, 11, 5, 17, 11, 3}

    {17, 7, 13, 12, 1, 2, 1, 17, 2, 6, 1, 11, 6, 3, 11, 5, 3, 11, 18, 11}

    Returns: 928013

  23. {3, 17, 20, 15, 17, 1, 1, 3, 9, 19, 2, 13, 16, 1, 9, 19, 1, 1, 5, 19}

    {14, 19, 13, 13, 9, 9, 5, 11, 10, 3, 3, 16, 20, 5, 1, 5, 19, 8, 17, 1}

    Returns: 1042654

  24. {7, 9, 17, 11, 1, 11, 3, 13, 11, 16, 16, 17, 3, 8, 15, 17, 17, 19, 1, 17}

    {20, 8, 9, 5, 11, 10, 18, 2, 3, 17, 17, 17, 5, 18, 3, 7, 6, 16, 1, 11}

    Returns: 1045575

  25. {1, 17, 1, 17, 16, 13, 3, 19, 13, 6, 16, 2, 5, 13, 16, 11, 1, 1, 15, 13}

    {1, 7, 1, 13, 1, 9, 1, 16, 17, 16, 19, 17, 13, 11, 5, 11, 1, 12, 5, 15}

    Returns: 1030691

  26. {17, 1, 11, 5, 1, 17, 1, 1, 16, 17, 2, 11, 4, 1, 1, 16, 1, 5, 10, 1}

    {3, 9, 1, 8, 3, 5, 13, 15, 9, 15, 12, 20, 2, 1, 18, 13, 13, 1, 20, 5}

    Returns: 980138

  27. {5, 14, 5, 11, 5, 13, 1, 9, 9, 3, 11, 6, 5, 1, 5, 1, 20, 1, 8, 17}

    {16, 6, 1, 14, 8, 17, 20, 1, 1, 19, 3, 1, 8, 5, 8, 1, 1, 13, 1, 1}

    Returns: 1032747

  28. {5, 16, 1, 9, 1, 4, 9, 5, 13, 17, 3, 8, 11, 1, 19, 20, 17, 6, 19, 16}

    {14, 13, 16, 13, 2, 10, 4, 11, 1, 1, 19, 9, 17, 5, 4, 1, 9, 1, 11, 18}

    Returns: 1034054

  29. {1, 11, 9, 9, 9, 13, 5, 2, 3, 16, 3, 1, 11, 13, 1, 17, 16, 13, 18, 17}

    {9, 16, 13, 10, 16, 17, 1, 13, 1, 16, 3, 5, 6, 9, 13, 17, 1, 17, 3, 18}

    Returns: 1025268

  30. {6, 20, 19, 5, 1, 9, 1, 1, 1, 9, 15, 4, 1, 14, 13, 16, 16, 11, 11, 13}

    {11, 16, 7, 13, 6, 11, 1, 15, 9, 17, 17, 12, 11, 3, 10, 5, 11, 1, 13, 18}

    Returns: 1031307

  31. {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20}

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

    Returns: 1048574

  32. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 1048574

  33. {13, 9, 12, 8, 10, 7, 16, 14, 17, 6, 5, 19, 11, 20, 2, 18, 3, 4, 1, 15}

    {13, 9, 12, 8, 10, 7, 16, 14, 17, 6, 5, 19, 11, 20, 2, 18, 3, 4, 1, 15}

    Returns: 1047962

  34. {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20}

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 0

  35. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    {19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19}

    Returns: 20

  36. {19, 12, 15, 17, 17, 15, 17, 19, 19, 13, 18, 10, 15, 18, 11, 14, 12, 18, 13, 18}

    {12, 19, 17, 15, 15, 17, 19, 17, 13, 19, 10, 18, 18, 15, 14, 11, 18, 12, 18, 13}

    Returns: 1048537

  37. {14, 18, 20, 10, 16, 15, 14, 20, 12, 14, 17, 11, 20, 18, 10, 10, 12, 14, 14, 12}

    {18, 14, 10, 20, 15, 16, 20, 14, 14, 12, 11, 17, 18, 20, 10, 10, 14, 12, 12, 14}

    Returns: 1048536

  38. {16, 12, 16, 10, 16, 18, 11, 13, 11, 13, 19, 20, 14, 14, 11, 20, 16, 16, 14, 20}

    {12, 16, 10, 16, 18, 16, 13, 11, 13, 11, 20, 19, 14, 14, 20, 11, 16, 16, 20, 14}

    Returns: 1048539

  39. {13, 16, 11, 12, 19, 12, 13, 13, 12, 18, 10, 15, 10, 20, 14, 20, 18, 18, 19, 10}

    {16, 13, 12, 11, 12, 19, 13, 13, 18, 12, 15, 10, 20, 10, 20, 14, 18, 18, 10, 19}

    Returns: 1048535

  40. {19, 16, 15, 19, 17, 13, 17, 12, 19, 12, 18, 10, 15, 10, 11, 14, 12, 11, 13, 13}

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 20

  41. {14, 12, 20, 19, 16, 10, 14, 18, 12, 11, 17, 12, 20, 14, 10, 14, 12, 13, 14, 18}

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 18

  42. {16, 17, 16, 10, 16, 11, 11, 19, 11, 19, 19, 16, 14, 19, 11, 12, 16, 15, 14, 17}

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 20

  43. {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20}

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

    Returns: 60459

  44. {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20}

    {9, 1, 1, 8, 6, 6, 11, 1, 5, 8, 2, 3, 9, 1, 1, 2, 5, 8, 3, 1}

    Returns: 6195

  45. {1, 1, 2, 4, 1, 3, 1, 3, 1, 3, 3, 4, 1, 4, 3, 1, 1, 3, 1, 1}

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

    Returns: 1046707

  46. {1, 1, 3, 1, 4, 1, 3, 1, 2, 1, 2, 1, 1, 2, 4, 2, 1}

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

    Returns: 127884

  47. {1, 3, 1, 4, 1, 1, 1, 4, 1, 1, 4, 3, 2, 1, 1, 3, 4}

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

    Returns: 127799

  48. {4, 4 }

    {4, 4 }

    Returns: 2

  49. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 1048574

  50. {1, 2, 3, 4, 5, 6, 7 }

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

    Returns: 98

  51. {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 }

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

    Returns: 1048574

  52. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

    Returns: 944024

  53. {10, 12, 3, 4, 5, 6, 7, 19, 17, 5, 4, 5, 3, 5, 3, 5, 3, 4, 5, 19 }

    {18, 17, 3, 3, 4, 5, 6, 17, 14, 15, 15, 18, 13, 14, 16, 19, 18, 17, 16, 2 }

    Returns: 604907

  54. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    {7, 6, 5, 4, 3, 2, 1, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    Returns: 1047962

  55. {1, 2, 3, 4, 5, 6, 7 }

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

    Returns: 78

  56. {1, 2, 3, 4, 5, 6, 7, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

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

    Returns: 1048458

  57. {11, 14, 12, 18, 13, 20, 20, 11, 13, 19, 13, 19, 15, 19, 12, 19, 16, 14, 11, 20 }

    {17, 12, 20, 19, 16, 16, 13, 17, 15, 16, 11, 19, 12, 13, 18, 18, 18, 17, 14, 17 }

    Returns: 1048451

  58. {5, 12, 10, 19, 2, 18, 8, 7, 7, 9, 5, 10, 14, 2, 11, 13, 17, 6, 15, 5 }

    {17, 18, 9, 3, 7, 4, 2, 4, 7, 19, 7, 13, 7, 15, 9, 11, 13, 17, 17, 19 }

    Returns: 1046299

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: