TopCoder problem "TheMoviesLevelThreeDivOne" used in SRM 469 (Division I Level Three)

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.


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


-timeJ will contain between 1 and 47 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.


{4, 4}
{4, 4}
Returns: 2
We are interested in two distributions where John and Brus get one movie each.
{1, 4}
{4, 2}
Returns: 1
Here the only possible distribution is where Brus gets the first movie and John gets the second one.
{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.
{1, 2, 3, 4, 5, 6, 7}
{7, 6, 5, 4, 3, 2, 1}
Returns: 98

Problem url:

Problem stats url:




PabloGilberto , Andrew_Lazarev , ivan_metelsky

Problem categories:

Dynamic Programming