duckduckMoose's blog

Tree/Graph problem; Any hints / ideas are welcomed
By duckduckMoose, history, 4 years ago, In English

Hi everyone. I've been struggling with this for some time now. Any ideas on how to approach this one.

Alice and Bob play a game, Initially, they reside in different cities, in a network of cities having a tree structure. The cities are numbered from 1 to N. Initially Alice resides in city 1, while Bob resides in city N. The game is played in turns with Alice making the first move.

In Alice's turn she will go to any city, adjacent to her current city, which is yet not visited by Alice or Bob and similarly, Bob in his turn will also go to any city not yet visited by him or Alice and is adjacent to his current city. The person who visits the maximum number of cities wins.

Given the N and the connections between cities, predict who wins.

Constraints: 1<=N<=10**5

Example:

N=4 Connections=[{1,2},{2,3},{2,4}]

Output: Alice

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

Comments Comments (6)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please provide the problem source.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As their map is the tree — there only one route between them. For each city on this route including initial we can calculate cost for turning away from it or move forward and choose the better one.

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

    Can you please elaborate, I am unable to follow.

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

      For every point on a route from city 1 to N you can calculate what score players would end up with, if Alice (for example) would turn away from this route (to the longest possible). Then the question is: can she get to the city on a route where her score would be higher than Bobs.

      → Reply