I cannot understand this question. Can anyone explain to me why the second example gives an output of 4? What is the moving strategy here? Thanks!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I cannot understand this question. Can anyone explain to me why the second example gives an output of 4? What is the moving strategy here? Thanks!
Name |
---|
Auto comment: topic has been updated by Ra1nWarden (previous revision, new revision, compare).
The graph looks like this (the numbers indicate the number of armies, just as in the problem statement, vertices with 0 armies are hostile).
The graph consists of two components. Note that for the first component, no movement can occur (we can not attack hostile vertices, and the vertex with 5 armies is otherwise isolated). This already gives us an upperbound of 5.
As for the second component. Note that from the vertex I marked with a *, we can move 1 army to the the other vertex with 3 armies, and 2 to the vertex with 2 armies. This creates a problem though: the *-vertex will have 0 armies. Because of this, we should first move some (anywhere from 1 to 6) armies from the 7-vertex to the *-vertex. This is allowed since as the problem statement says, we can do the movements one by one. The sequence thus is: move 1 army from the 7-vertex to the *-vertex; move 1 army from the *-vertex to the other 3-vertex; move 2 armies from the *-vertex to the 2-vertex.
The result is this:
So this is a solution with ""strength"" 4. It should be easy to see this is optimal.
Thanks for the explanation! Why can't we move 5 more army from 6 to 1 and then allocate them to the two 4s?
Because in each turn, armies can only move to adjacent vertices.
Then at the beginning, can't you transfer 6 armies from 7 to *-vertex and then allocate armies on the *-vertex (has 6 + 3 = 9 armies now) to the border ones? Sorry, I still did not get it.
Then you would have some armies moving twice, but each army may only move once and only to an adjacent vertex.
I see. That makes it clear. Thanks!