[Solved]: Is there a more efficient algorithm than backtracking/dynamic programming?

Problem Detail: 

Consider the following game:

One day a castle is attacked at sunrise (by surprise) by n soldiers.

Each soldier carries a canon and a rifle.

The castle has strength s.

On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points). After all the soldiers have fired, the castle sends dpw defenders to battle them.

In the ensuing days the castle and the soldiers battle it out following these rules:

1. All the soldiers fire first. A soldier can fire his canon at the castle or his rifle at one of the defenders (but not both and each soldier can only shoot once). One shot at a defender kills him. One shot at the castle decreases its strength by 1.

2. Then each of the d defenders shoots at one soldier (and only one) killing him.

3. If the castle still has strength points (i.e. s>0) it sends a new batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.

4. Repeat 1 through 3 on each new day.

5. If all soldiers are killed by the defenders, the castle wins.

6. If there are zero defenders after the soldiers shoot and the castle strength is zero, the soldiers win.

We would like to know the minimum number of rounds the soldiers need to win the game (or if not possible the minimum number of rounds for the castle to win the game).

We would also like to know the number of soldiers, defenders and castle strength at the beginning of each round for the minimum number of rounds solution.

An easy way to solve this problem seems to me to be by recursive backtracking/depth first search or dynamic programming.

The problem however seems simple enough that a better/faster solution seems likely to exist (one that doesnt involve a large search or maybe even a search at all).

Is it obvious what that better strategy/algorithm might be?

Asked By : user35202

Answered By : Kittsil

(Throughout this answer I use $\phi = \frac{1+\sqrt{5}}{2}$, which is the Golden Ratio.)

Solution:

• If $s\leq n$, the attackers can win in one day.
• If $s+dpw<\phi^2n$ and $s<2n$, the attackers can win in $2+\max(k,0)$ days, where $$k=\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil.$$
• If $dpw<n$, the attackers can win in $c+\max(k,0)$ days, where $$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil$$ and $$k = \left\lceil\frac{\log_\phi{\left(\frac{n+(s + c\cdot dpw-(c+1)n)\phi^{-1}}{n-(s + c\cdot dpw-(c+1)n)\phi}\right)}}{4}\right\rceil.$$
• If the attackers cannot win, the minimum number of days for the castle to win is $2$ (the attackers all fire their cannons and are wiped out on day two).

Proof:

For a given day $i$, let $s_i$ be the remaining castle strength, $a_i$ be the remaining attacking force, and $d_i$ be the remaining defending force.

First consider the case that $d_i = dpw$ (that is, the attackers killed all defenders the day before). Assume that the attackers leave $x$ defenders alive but do not destroy the castle; then $$a_{i+1} = a_i-x;$$ $$d_{i+1} = dpw+x;$$ $$s_{i+1} = s_i-(a_i-(dpw-x)) = (s_i+dpw)-(a_i+x).$$ On day $i+1$, the defending force is larger than on day $i$ and the attacking force is smaller than on day $i$. Furthermore, even if the attackers return to the strategy of wiping out the defending force on day $i+1$, $$a_{i+2} = a_i-x;$$ $$d_{i+2} = dpw;$$ $$s_{i+2} = s_{i+1}-(a_{i+1}-d_{i+1}) = s_i+2dpw+x-2a_i.$$ If, instead, the attackers had wiped the defending force on day $i$, the castle's strength would be $s_i+2dpw-2a_i$. Therefore, it is never advantageous to leave both defenders and the castle alive on the same day. (Note that if $s_i+2dpw+x-2a_i<0$ -- that is, they destroyed the castle on day $i+1$ -- they could have have done the same thing without losing troops; therefore, while it might not always be disadvantageous, it is never advantageous.)

Now the question is, when the attackers do destroy the castle, how many days will it take to kill the remaining defenders (with the obvious assumption that the attackers would not make a final push on the castle unless they can still win)? Assume, without loss of generality, that the castle is destroyed on day $q$ and that there are $x$ defenders remaining alive. So $$d_{q+1} = x;$$ $$a_{q+1} = n-x;$$ $$d_{q+2} = d_{q+1}-a_{q+1} = 2x-n;$$ $$a_{q+2} = a_{q+1}-d_{q+2} = 2n-3x;$$ $$d_{q+3} = d_{q+2}-a_{q+2} = 5x-3n;$$ $$\dots$$ From this we can see that $d_{q+i+1} = Fib(2i+1)x-Fib(2i)n$. Therefore, (finding the closed form of $Fib(\cdot)$ and four pages of algebra later), the attackers will win $$k = \left\lceil\frac{\log_\phi{\left(\frac{n+x\phi^{-1}}{n-x\phi}\right)}}{4}\right\rceil$$ days after destroying the castle. $x = s'+dpw-n$, where $s'$ is the strength of the castle on the day it is destroyed.

On every day that the attackers can make a final push on the castle, the question is, "Would it be advantageous to wait until tomorrow?" Every day (after the first) that the attackers do not make a final push, the castle's strength decreases by $n-dpw$. Therefore, at the beginning of the day of the final push (day $i$), $s' = s-n-(i-1)(n-dpw)$, so $x_i = dpw-(n-s') = $ $s + i\cdot dpw-(i+1)n$ (where $x_i$ is the remaining defending force if the attackers pushed on day $i$). It is advantageous to wait another day if $$ \frac{\log_\phi{\left(\frac{n+x_{i+1}\phi^{-1}}{n-x_{i+1}\phi}\right)}}{4} + 1 < \frac{\log_\phi{\left(\frac{n+x_i\phi^{-1}}{n-x_i\phi}\right)}}{4},$$ that is, when one more than the number of days to destroy the $x$ beginning on day $i+1$ is less than the number of days to destroy $x$ beginning on day $i$. Three pages of algebra later, we find that it becomes advantageous to destroy the castle on the day $$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil.$$

After destroying the castle, we still have to kill the troops, so the total number of days is $c+k$, using $i=c$ to find $k$.

Finally, we must handle the edge case that $dpw \geq n$. Intuitively, the attackers can only be victorious only if they can destroy the castle on the first day of fighting (day 2) with enough troops left to defeat the remaining defenders. This can only happen if $s<2n$ (they can destroy the castle by the end of the second day) and if $s+dpw<(\phi+1)n$ (they can destroy the castle and do enough damage that the defenders cannot effectively retaliate); it will take $\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil$ days to kill the rest of the defenders.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44868