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.



  • 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?

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.


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

I had the same problem too and I checked out some music blog and finally found solution here, nice one,