Блог пользователя Ra1nWarden

Автор Ra1nWarden, история, 9 лет назад, По-английски

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!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Ra1nWarden (previous revision, new revision, compare).

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The graph looks like this (the numbers indicate the number of armies, just as in the problem statement, vertices with 0 armies are hostile).

  0---5
  
    7
    |
    3*
   / \
  3---2
   \ /
    0
 

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:

  0---5
  
    6
    |
    1
   / \
  4---4
   \ /
    0
 

So this is a solution with ""strength"" 4. It should be easy to see this is optimal.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the explanation! Why can't we move 5 more army from 6 to 1 and then allocate them to the two 4s?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Because in each turn, armies can only move to adjacent vertices.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Then you would have some armies moving twice, but each army may only move once and only to an adjacent vertex.