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
Please provide the problem source.
A similar task was given in kickstart round E 2020. Not completely sure.
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.
Can you please elaborate, I am unable to follow.
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.
Thanks a lot!!! Got your solution.