Optimal strategy for the following game

I got stuck on this problem in the context of dynamic programming:

There are n tasks, each of them has a time it takes to finish it and a reward (amount of money the player that finishes the task gets). The tasks are not atomic, meaning that for example a task with time 10 can be solved by spending 5 time units during 2 different rounds. So it is possible to solve a task partially but ONLY the player who finishes the task get’s the money. In other words, only the player who sets the time of the task to 0 (or bellow) gets the reward/money for that task.

There are 2 players (let’s call them A and B). Each player has a block of time which he can spend on exactly one task per round (a player can not spend his time on 2 different tasks during 1 round), players can have time blocks of different sizes. Players B strategy is always the same: on his turn during the round, he picks the task with the lowest amount of time left and spends his time block on that task. Player A can pick whichever task he wants, he can also skip rounds. During each round player A goes first (player A picks a task or skips the round, then player B picks a task).

For given:

  • Player A time per round (amount of time player A can spend on exactly one task per round),
  • Player B time per round (-||-),
  • n tasks with T (time required to finish the task) and M (money a player gets for finishing the task),

determine the optimal strategy for A such that the amount of money he wins is maximized. Output the maximal amount of money player A can win.

Example:

Given:

  • A time per round: 4
  • B time per round: 5
  • task1 (T=9, M=5)
  • task2 (T=6, M=2)
  • task3 (T=7, M=3)

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

Explanation: round1: player A skips this round, player B picks task 2 (now task2 has T=6-5=1), round2: player A picks and finishes task 2, player B picks task 3, round3: player A picks and finishes task 3, player B picks task 1, round 4: player A picks and finishes task 1. All tasks are finished, player A is left with 5+2+3=10 money.

Can this problem be reduced to some other well-known problem? Can you explain to me how I could solve this or point me to some website which can help me to understand the solution to this problem?

Instead of posting the question why don’t you share the link?

@hruday968 I encountered the problem during a contest at my school, I don’t have the problem statement :confused: This is what I have from notes/memory and is an adequate description of the problem I hope, give me a chance to clarify if any part of the problem seems unclear.

What are the constraints on n ?

1 Like

@hemanth_1 1<=n<=50

All the inputs are <= 100

The task is really interesting.
On this website I relatively recently. I was really surprised by the abundance of interesting tasks.
And I racked my brains, but the answer on your question in the process.

Regards,
Pat

//