0
$\begingroup$

Given an array of length n filled with objects which contain 2 ints (size and reward).

Now 2 players are taking turns, each player has an int value we call strength. Let's call them player A and player B, player A goes first.

Player A can pick whichever object from the array he wants and decrease the size of the object by his strength (pickedObj.size -= playerA.strength), he can also skip his turn by simply not picking an object.

Player B is simple minded and for all his turns uses the same greedy strategy: he picks the object with the smallest size and decreases it's size by his strength (pickedObj.size -= playerB.strength), player B can't skip turns.

Once a player decreases the size of an object to 0 (or bellow) he receives the reward (playerX.reward += finishedObj.reward) associated with that object. Each player starts with 0 reward points (playerX.reward = 0).

Given an array with n objects, player A with strength = m and player B with strength = k, compute the maximal amount of reward points that player A can win.

Examples:

Example 1:

obj[] array = `{ (9,5), (6,2), (7,3) }`;
playerA.strength = 4;
PlayerB.strength = 5;

int solution = determineMaxReward(array, 4, 5);

// The solution (max amount of money player A can win) is 10.

Explanation:

  1. Round 1: Player A skips this round, player B picks arr[1] and therefore decreases it's size by his strength (now arr[1] = (1,2)).
  2. Round 2: Player A picks and finishes arr[1] (playerA.reward += 2), player B picks arr[2] (arr[2] = (2,3))
  3. Round 3: Player A picks and finishes arr[2] (playerA.reward += 3), player B picks arr[0] (arr[0] = (4,5))
  4. Round 4: Player A picks and finishes arr[0] (playerA.reward += 5)

That's an optimal game for player A, the at the end he is left with 10 reward points which is the maximal amount of reward points he can possibly achieve.

Example 2:

obj[] array = `{ (2,1), (2,5) }`;
playerA.strength = 1;
PlayerB.strength = 2;

int solution = determineMaxReward(array, 1, 2);

// The solution (max amount of money player A can win) is 5.

Example 3:

obj[] array = `{ (9,3), (10,3), (4,1), (8,1), (9,2) }`;
playerA.strength = 5;
PlayerB.strength = 3;

int solution = determineMaxReward(array, 5, 3);

// The solution (max amount of money player A can win) is 10.

My current unproven (in the sense of optimality) approach:

For each object, I compute the minimal number of picks player A needs to make in order to finish that object. Then I reduce to the knapsack problem, size of the knapsack being the number of picks player A can do during the game, then the best way to fit the objects with their size and reward into the knapsack (such that the reward is maximized) is found.

Now I'm not sure if this is optimal, I can't find a counterexample where my approach doesn't work but I also can't prove that it's optimal. Any help/comments are appreciated.

This is a problem I have been struggling with for a while now, I encountered it during a programming contest in the context of dynamic programming.

$\endgroup$
  • $\begingroup$ Can you credit the source of the problem? In particular, can you edit the question to provide the name of the programming contest, with a link to it (if possible)? Is the contest still ongoing? $\endgroup$ – D.W. Jul 9 '17 at 16:22
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving contest problems for you is unlikely to achieve that. You might find this page helpful in improving your question. (continued) $\endgroup$ – D.W. Jul 9 '17 at 16:23
  • $\begingroup$ You tagged it with dynamic-programming. We've written some general reference information on how to approach dynamic programming problems: cs.stackexchange.com/tags/dynamic-programming/info. I suggest you try working through the systematic approach listed there, step by step, then if you're still stuck, edit the question to show what progress you made and at what point you got stuck. What possible decomposition into "subproblems" have you tried so far? Can you write an inefficient (exponential-time) recursive algorithm to solve this? $\endgroup$ – D.W. Jul 9 '17 at 16:24
  • $\begingroup$ @D.W. The contest is long over (it was contest at my school), the problem statement isn't written in english, this post is my translation of it. I encountered the problem in the context of dynamic programming which is why I set it as a tag. Thanks for the additional info! $\endgroup$ – Anna Vopureta Jul 9 '17 at 18:59
  • $\begingroup$ Does the problem give ranges for the sizes and strengths? Because there's many ways this can be optimized, and a purely optimal solution seems really difficult. $\endgroup$ – DanielV Jul 9 '17 at 19:58
1
$\begingroup$

The key observation is that, for player A, picking an object which is not being picked by player B is equivalent to skipping the turn and saving this pick for later (for example use a variable savedPicks). Now instead of having to decide upon which object to pick the problem becomes deciding if player A should pick the current object picked by player B or save the pick for later. So we iterate through the objects depending on how player B picks them and either also pick the object as he does or save a pick for later.

Now the problem is solvable with DP, observe that your state consists of the current object which is targeted by player B, the remaining size of the object and the number of picks player A has saved.

There are three transitions:

  1. Object is finished, move to the next one,
  2. Player A skips the round and saves a pick for later (savedPicks++),
  3. Player A uses a saved pick to pick the current object (potentially getting the reward if his pick finished the current object).

Solve each of the three transitions, apply memoization (save already computed states, use a 3 dimensional array for example), don't forget the base case (all objects have been finished).

Happy coding!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.