There are $n \in \mathbb{N}$ towers, each with a height and a value. Let the positive integers $h_1, h_2, \dots, h_n$ be the heights and $v_1, v_2, \dots, v_n$ be the values, respectively. Two players $A$ and $B$ take turns. Player $A$ may or may not select an arbitrary tower and reduce it's height by $a \in \mathbb{N}$ units. Player $B$ always reduces the height of the tower with minimal index and height $\ge 1$ by $b \in \mathbb{N}$ units. If one of the players reduces the height of any tower $i$ to $< 1$, the value $v_i$ is rewarded to that player and the corresponding tower cannot be reduced anymore.

Question. What is the maximum reward player $A$ can get, assumming player $A$ starts?

Since I practice algorithms and want to implement it, the solution should be fast enough under given constraints (they are roughly $n, h_i, v_i, a, b \le 100$).

Example. Let $n = 5$, $a = 4$ and $b = 3$. The heights are $h_1 = 9$, $h_2 = 10$, $h_3 = 4$, $h_4 = 8$, $h_5 = 9$ and the values are $v_1 = 3$, $v_2 = 3$, $v_3 = 1$, $v_4 = 1$, $v_5 = 2$. Player $A$ can get the full reward of $10$ by skipping some turns and reduce tower by tower.

I present my obversations as following.

If we find an optimal strategy, we can answer the question by simulating it. This surely satisfies the constraints, because there are at most $2 \cdot 100^2 = 20\,000$ turns (player $A$ always skips).

Since the behaviour of player $B$ is completely determined by the behaviour of player $A$, the problem comes down to find a sequence of decisions which tower to reduce. Unfortunately, there are up to $n$ options in each turn and the decision tree grows exponentially $-$ too slow.

Maybe, we can apply dynamic programming. Denote $dp(i, k)$ the maximum reward player $A$ can get when playing on the towers $i, i + 1, \dots, n$ and player $A$ may perform $k$ consecutive turns, before player $B$ has the first turn and the game goes on alternating. Thus, our final answer is $dp(1, 1)$. We compute our dp table in the following topological ordering: $dp(n, k), dp(n - 1, k), \dots, dp(1, k)$, each one for $1 \le k \le k_{max}$, where $k_{max}$ is upper bound for the number of turns required to retrieve the values from all towers, i.e. play the game alone and acquire maximum reward. Now, we may somehow distinguish two cases:

  • Player $A$ gets the reward from tower $i$
  • Player $A$ does not get the reward from tower $i$

In the second case, player $B$ reduces tower $i$ alone and needs say $x$ turns. Then player $A$ may use his $x$ turns on the rest and acquires $dp(i + 1, k + x)$ reward. However, I don't know how to proceed from here and handle the first case (does this dp approach even make sense?)

Hints and analysis are highly appreciated.

  • 1
    $\begingroup$ Can you credit the source where you encountered this problem? $\endgroup$ – D.W. Oct 15 '17 at 23:40

Your Answer

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

Browse other questions tagged or ask your own question.