Connection Status:
Competition Arena > HeavyBooks

HeavyBooks

TCO12 Round 2B · 2012-03-27 · by meret

TCO12 Round 2B · 2012-03-27 · by meret · Dynamic Programming, Greedy
Class Name: HeavyBooks
Return Type: int[]
Method Name: findWeight
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Warning: This problem statement contains superscripts and/or subscripts. It may not display properly outside of the applet.


Tomek and Wojtek are going to participate as a team in their local ICPC competition next week. The organizers allow the contestants to bring their own printed materials such as books to the contest site. Their university has some books they could borrow; the i-th of those books weighs books[i] grams. Our heroes would like to have as much material available as possible, however neither of them wishes to be carrying too much weight. Let T be the total weight of books that Tomek will take, and W be the total weight of books that Wojtek will take. Then, Tomek wants to maximize W - T, while Wojtek wants to maximize T - W; if they would have multiple optimal choices, both of them want to maximize T + W as a tie-breaker. The way it will be decided who carries which books to the contest will be as follows:

  • First, Tomek selects any moves[0] books from the library, and put them in Wojtek's backpack. These will be the books that their team will take to the contest.
  • Then, Wojtek selects any moves[1] books from his backpack, and moves them to Tomek's backpack.
  • Then, Tomek selects any moves[2] books from his backpack, and moves them to Wojtek's backpack, and so on...
This process continues for a total of n moves, where n is the number of elements in moves. If there are less than moves[i] books available in the i-th move, the player simply moves all the available books.

You are given a int[] books and a int[] moves. Return a int[] containing exactly two elements, (T, W), with the first element equal to the total weight of books that Tomek will carry, and the second element equal to the total weight of books that Wojtek will carry. Assume that both Tomek and Wojtek make optimal choices during the process described above.

Notes

  • The books may be very heavy.
  • The correct return value is always uniquely determined by the problem statement.

Constraints

  • books will contain between 1 and 50 elements, inclusive.
  • Each element of books will be between 1 and 106, inclusive.
  • moves will contain between 1 and 50 elements, inclusive.
  • Each element of moves will be between 1 and the number of elements in books, inclusive.
Examples
0)
{5,2,3,1}
{3,2,1,1,1}
Returns: {3, 7 }

The process can go as follows: First, Tomek will pick books with weights 5, 2 and 3 and put them in Wojtek's backpack. Wojtek will move the books with weights 5 and 3 to Tomek's backpack. Tomek will move the book with weight 5 back to Wojtek's backpack. Wojtek will move the book with weight 5 back to Tomek's backpack. Finally, Tomek will move the book with weight 5 back to Wojtek's backpack again.

1)
{10, 100, 1000}
{2, 3}
Returns: {110, 0 }

Wojtek has only two books after Tomek's opening move, so he empties his backpack in his move.

2)
{62986}
{1}
Returns: {0, 62986 }
3)
{9464,11509}
{1,1}
Returns: {9464, 0 }
4)
{61606,318286,353139}
{1}
Returns: {0, 353139 }
183)
{500,500,500,500}
{4,1,1,3,2}
Returns: {500, 1500 }

Here, all the books have the same weight.

Submissions are judged against all 407 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HeavyBooks with a public method vector<int> findWeight(vector<int> books, vector<int> moves) · 407 test cases · 2 s / 256 MB per case

Submitting as anonymous