Mythic07's blog

Please! Help me find this problem.
By Mythic07, history, 13 months ago, In English

I'm searching for a problem which goes like this...

Given a graph with n vertices and m edges, all the vertices has some value associated with them. We as Player 1, makes the first move and removes exactly one vertex from the graph. The opponent as Player 2, makes a move and select any one component of their choice from the available ones. Then, we make our 2nd move and select any one component from the remaining ones (it is possible that there is nothing left for us). The score of any player is defined as the sum of values of vertices in their component.

Our goal is to maximize our own score, considering that the opponent plays OPTIMALLY.

Someone mentioned that they have seen this problem either on CF or LC, but I'm unable to find it. I have a solution that passed all the cases that i could think of but I want to be sure that this is the correct and optimal one.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

ㅤ

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for mentioning but this is not what I'm looking for

    → Reply