4
$\begingroup$

The problem

Trying to improve my algorithms I bumped into a problem by Pedro Pablo Gómez Martín and Marco Antonio Gómez Martín, which I can summarise like this:

You are given a list of enemy bases you want to conquer. You can only attack one base at a time. Each base $i$ requires a minimum number of soldiers $s_i$ to be conquered, will take out a certain number $b_i$ of the soldiers who attack and will require a certain number $r_i$ of soldiers to stay back holding it, as you move the remaining army to the next battle.

The following relationship will always hold for a base $i$: $s_i \geq b_i$. Note that it is possible that $r_i \gt s_i$.

Determine the best sequence to follow in order to minimize the number of soldiers needed to conquer all bases.

I know, given a certain order, how to compute the number of soldiers needed, and the solution space is finite, so brute-forcing it is always a possibility, but far from ideal. It looks like there is a greedy algorithm to find the right order.

My work

Finding the minimum number of soldiers needed for a given order

I found a series of inequations which I believe give me the number of soldiers $x$ needed to conquer and hold $n$ bases if attacked in from $1$ to $n$:

  • We need enough soldiers to conquer the first base: $x_{a} = s_1$
  • Before each subsequent battle, we need enough soldiers to take it after all the losses of the previous battles: $x_{b} = \max\limits_{2 \leq i \leq n} ( s_i+\sum\limits_{j=1}^{i-1}(b_j+r_j))$
  • We want enough people to survive to be able to keep the last base: $x_{c} = \sum\limits_{i=1}^{n}(b_i+r_i)$

So I believe the minimum number of soldiers needed $x$ to hold and retain all is $x = max(x_{a}, x_{b}, x_c)$. I think these equations can be used to prove that a certain order is optimal or not, though how exactly escapes me.

Finding the right order to minimise the number of soldiers needed

The key insights I figured out are:

  • The army gets weaker with each battle, so the battles which require more people should be fought first, when the army is at its strongest (decreasing order of $s_i$).
  • The losses matter more the sooner they happen. Hence, we should first fight the battles which will immobilise the least number of soldiers (increasing order of $b_i + r_i$).

Neither criterion by itself is enough to find the optimal solution in all cases.

My question

The proper solution seems to be combining the previous two insights into a single metric: decreasing order of $si - (b_i + r_i)$. Attacking the bases in that order seems to guarantee a minimum number of soldiers needed, or at least that's what my tests indicate.

While I get an intuititon of how that way "combines" both insights, I can't figure out why it guarantees the optimal order. Why that metric and not, for example, decreasing order of $\frac{s_i}{b_i+r_i}$? Or some weighted combination?

I'd appreciate some help both proving mathematically that it is optimal (using my equations or some other way), and ideally gaining some intuition.

$\endgroup$
2

2 Answers 2

3
$\begingroup$

Okay! In order to (hopefully) prove that your proposed greedy algorithm is correct, we will make an argument that is very common when dealing with greedy algorithms (as you can see from @D.W. 's linked question).

So, suppose you have found an $x$ such that there exists at least one sequence of battles where the army will survive. That is, there is some sequence of battles $\mathcal{B} = (s_1,b_1,r_1),\ldots,(s_n,b_n,r_n)$, such that we have $x \geq \sum_{j=1}^{i-1} (b_j+r_j)+s_i$ for all $i$ and also $x \geq \sum_{i=1}^n (b_i+r_i)$. Then we also have the sequence of battles given by your greedy algorithm: $\mathcal{B'} = (s_1',b_1',r_1'),\ldots,(s_n',b_n',r_n')$. And we want to show that if the army survives sequence $\mathcal{B}$, then they also survive sequence $\mathcal{B'}$.

To do so, we look at the smallest index $k$ where $(s_k,b_k,r_k) \neq (s'_k,b'_k,r'_k)$. Since these are just two different orderings of the same battles, there is some $t>k$ such that $(s_t,b_t,r_t) = (s'_k,b'_k,r'_k)$. Now, the idea is to change the ordering such that $(s_t,b_t,r_t)$ comes between $(s_{k-1},b_{k-1},r_{k-1})$ and $(s_k,b_k,r_k)$.

Now, what happens if the army does not survive this modified sequence? That means that there is some other index $i$ such that $x-(s_i+(b_t+r_t)) < \sum_{j=1}^{i-1} (b_j+r_j)$. It should quickly be clear that $k\leq i<t$ (therefore we did not overcount the battle at index $t$ in the previous formula). But what does this imply for the original sequence, where the battle at index $t$ came at index $t$?

Since $(s_t,b_t,r_t)$ was equal to $(s_k',b_k',r_k')$ in the greedily generated sequence, and the two sequences were equal for all indices lower than $k$, we can infer that $(s_i,b_i,r_i) = (s_{i'}',b_{i'}',r_{i'}')$ for some $i'>k$. From the way the battles were sorted in $\mathcal{B'}$, we therefore know that $s_t-(b_t+r_t) \geq s_i-(b_i+r_i)$. Reordering gives $s_t+(b_i+r_i) \geq s_i+(b_t+r_t)$. Putting it all together, we get this inequality: $x-(s_t+(b_i+r_i)) \leq x-(s_i+(b_t+r_t)) < \sum_{j=1}^{i-1} (b_j+r_j) \leq \sum_{j=1}^{t-1} (b_j+r_j)-(b_i+r_i)$.

This means that the army would not survive the original sequence of battles, $\mathcal{B}$! This calculation was derived from the assumption that the army did not survive the modified sequence; therefore that assumption must be wrong.

Now we know that as long as the chosen sequence differs from the greedy sequence at least at one point, we can just move the greedy choice to that point and still get a sequence where the army survives. Therefore the greedy sequence itself must always be among those where the army survives. Note that the trick with looking at the first index where the two sequences differ is a standard trick when proving greedy algorithms correct, and it is well worth it to familiarize oneself with this technique.

$\endgroup$
2
$\begingroup$

@Highheath has given an excellent and concise answer already.

I came up (with the help of some friends) with a much longer one, which I still think it's worth posting. Maybe it's because I worked on it for a few hours, but I find it easier to comprehend despite its length.


It is important to distinguish the purpose of $s_i$, $b_i$ and $r_i$. $s_i$ represents the number of people needed to win battle $i$. You may win a battle but not be able to hold the base: if you have $m$ soldiers march into battle $i$, after the battle you have $m-b_i$ soldiers alive, and if $m-b_i \lt r_i$, you will not be able to hold the base. So $s_i$ simply represents the number of people needed to win the battle, not not necessarily to hold the base afterwards.

For simplicity, let's call $l_i=b_i+r_i$ to the loss of people in battle $i$, i.e. the number of soldiers which are not available for further battles after battle $i$, because they were casualties or had to stay behind holding the base.

Corollary 1

For $n=2$, sorting in descending order of $s_i - l_i$ results in the minimum number of soldiers needed.

Let's take two bases, called $B_a$ and $B_b$.

$B_a$ requires $s_a$ soldiers to be taken, and will incur in a loss of $l_a$. Similarly, $B$ requires $s_b$ soldiers, and will incur in a loss of $l_b$ soldiers.

Let's state that $s_a - l_a \geq s_b - l_b$. This means that $s_a + l_b \geq s_b + l_a$ (1).

Case 1: We attack $B_a$ before $B_b$.

In order to guarantee winning all battles and holding all bases, we need:

  • Enough soldiers to win the first battle: $s_a$
  • Enough soldiers to win the second battle after the first one: $s_b+l_a$
  • Enough soldiers to withhold all casualties and soldiers left behind: $l_a+l_b$ $$x_1 = \max(s_a, s_b+l_a, l_a+l_b)$$

Case 2: We attack $B_b$ before $B_a$.

In order to guarantee winning all battles and holding all bases, we need:

  • Enough soldiers to win the first battle: $s_b$
  • Enough soldiers to win the second battle after the first one: $s_a+l_b$
  • Enough soldiers to withhold all casualties and soldiers left behind: $l_a+l_b$ $$x_2 = \max(s_b, s_a+l_b, l_a+l_b)$$

Let's consider all three values that $x_1$ might take, and realise that in all cases, $x_2 \geq x_1$. We can do this by seeing that, for any value $x_1$ takes, there is at least one value in the three possible values which $x_2$ may take which is greater or equal than $x_1$, so $x_2 \geq x_1$:

  • If $x_1 = s_a$, $x_2$ will be at least $s_a+l_b$
  • If $x_1 = s_b + l_a$, we know that one of the values of $x_2$, $s_a+l_b$, is greater than $x_1$ (see (1))
  • If $x_1 = l_a + l_b$, $x_2$ will be at least $l_a + l_b$

So it is proven that, given two bases, is optimal to attack them in decreasing order of $s_i - l_i$.


Lemma 1

The optimal relative order of $B_a$ and $B_b$ ($B_a$ attacked before $B_b$) remains the same if a third base $B_c$ is inserted between the two, provided that $s_a - l_a \geq s_c - l_c \geq s_b - l_b$

We can prove this by comparing the two alternatives:

Case 1: $B_a \rightarrow B_c \rightarrow B_b$

We need enough soldiers to:

  • Take the first base: $s_a$
  • Take the second base after the first battle: $s_c + l_a$
  • Take the third base after the first two battles: $s_b + l_a + l_c$
  • Survive all losses: $l_a + l_b + l_c$

$x_{1}=\max(s_a, s_c+l_a, s_b+l_a+l_c, l_a+l_b+l_c)$

Case 2: $B_b \rightarrow B_c \rightarrow B_a$

We need enough soldiers to:

  • Take the first base: $s_b$
  • Take the second base after the first battle: $s_c + l_b$
  • Take the third base after the first two battles: $s_a + l_b + l_c$
  • Survive all losses: $l_a + l_b + l_c$

$x_{2}=\max(s_b, s_c+l_b, s_a+l_b+l_c, l_a+l_b+l_c)$

We can prove that $x_{1} \leq x_{2}$ using the same method as for Corollary 1: for any possible value of $x_{1}$, the value of $x_{2}$ will be greater or equal than that.

  • If $x_{1}=s_a$, $x_{2}$ will be at least $x_{2}=s_a+l_b+l_c$
  • If $x_{1}=s_c+l_a$, $x_{2}$ will be at least $x_{2}=s_a+l_b+l_c$. This is because $s_a - l_a \geq s_c - l_c$, so $s_a + l_c \geq s_c + l_a$, and therefore, $s_a + l_b + l_c \geq s_c + l_a$
  • If $x_{1}=s_b + l_a + l_c$, $x_{2}$ will be at least $x_{2}=s_a+l_b+l_c$. This is because $s_a-l_a \geq s_b-l_b$, so $s_a+l_b \geq s_b+l_a$. By adding $l_c$ to both sides of the inequation, $s_a+l_b+l_c \geq s_b+l_a+l_c$
  • If $x_{1}=l_a + l_b + l_c$, $x_{2}$ will be at least $x_{2}=l_a+l_b+l_c$.

So, as long as $s_a - l_a \geq s_c - l_c \geq s_b - l_b$ holds, $B_a$ must be attacked before $B_b$.


Lemma 2

Given a sequence of battles, we can replace them with a single equivalent battle

We can prove this by induction, starting with $n=2$. Given two battles $B_j$ $(s_j, b_j, r_j)$ and $B_k$ $(s_k, b_k, r_k)$, we can say the following:

  • In order to win both battles, we need enough soldiers to win the first one and to win the second one after the first one: $s_{jk}=\max(s_j, s_k+l_j)$.
  • After fighting both battles, $b_{jk}=b_j + b_k$ soldiers will have been taken out.
  • After fighting both battles, $r_{jk}=r_j + r_k$ soldiers will be posted to keep the bases.

Note that $s_{jk}$ does not include the requirement of having enough people to hold all bases, because $s$ only represents the number of people needed to win a battle.

So we can replace the sequence with an equivalent battle $B_{jk}$ $(\max(s_j, s_k+l_j), b_j + b_k, r_j + r_k)$

For any value of $n \ge 2$, we can simply iteratively reduce the first two battles into one until only one base is left.


Lemma 3

For a sequence $B_1 \rightarrow B_2 \rightarrow ... B_{n-1} \rightarrow B_{n}$ sorted in decreasing order of $s_i-l_i$, if the middle sequence of $n-2$ bases is replaced with their single equivalent base $B_2'$, the resulting $B_1 \rightarrow B_2' \rightarrow B_{n}$ sequence is also in decreasing order of $s_i-l_i$

First we'll prove this for $n=4$. Let's start the demonstration with four bases sorted in decreasing order of $s_i-l_i$, $B_1 \rightarrow B_2 \rightarrow B_3 \rightarrow B_4$.

We know that the following inequalities are true: $s_1 - l_1 \geq s_2 - l_2 \geq s_3 - l_3 \geq s_4 - l_4$

We replace $B_2 \rightarrow B_3$ with $B_{23}$, with $s_{23}=\max(s_2, s_3+l_2)$ and $l_{23}=l_2+l_3$ (Lemma 2):

$B_1 \rightarrow B_{23} \rightarrow B_4$

We want to prove that the following relationship holds: $s_1 - l_1 \geq s_{23} - l_2 - l_3 \geq s_4 - l_4$

For this we, once again, examine the possible values of $s_{23}$:

Case 1: $s_{23}=s_2$

We want to prove: $s_1 - l_1 \geq s_2 - l_2 - l_3 \geq s_4 - l_4$, which has two parts:

Since $s_1 - l_1 \geq s_{2} - l_2$, trivially $s_1 - l_1 \geq s_{2} - l_2 - l_3$.

On the other hand, if $s_{23}=s_2$, we know that $s_2 \geq s_3 + l_2$ (or $s_{23}$ would have taken a different value). By adding the two known inequalities $s_3 - l_3 \geq s_4 - l_4$ and $s_2 \geq s_3 + l_2$, we reach $s_3 - l_3 + s_2 \geq s_4 - l_4 + s_3 + l_2$. Simplifying and reordering, we reach $s_2 - l_2 - l_3 \geq s_4 - l_4$.

Case 2: $s_{23}=s_3+l_2$

We want to prove: $s_1 - l_1 \geq s_3 - l_3 \geq s_4 - l_4$, which we already know to be true.

This ends the proof for Lemma 3 for $n=4$. This is trivially generalisable to $n>4$: first, replace $B_2$ and $B_3$ with their single equivalent base $B_{23}$, and that should leave the sequence still in order. Then replace $B_{23}$ and $B_4$ with $B_{234}$, etc.


Conclusion

We have proven that, if we sort our list of bases according to the $s_i - l_i$ (i.e. $s_i - (b_i+r_i)$) criterion, for any two distinct bases $B_i$ and $B_j$ that we choose, their relative order will be optimal:

  • If they are consecutive, the optimality is proven by Corollary 1.
  • If they are not consecutive, the bases in the middle can be reduced to a single equivalent base (Lemma 2), and the resulting sequence will still be sorted according to our criterion (Lemma 3). In that case, the optimality is proven by Lemma 1.

Since all bases are optimally sorted with respect to all other bases, the sorting of the whole list is optimal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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