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

Автор duckduckMoose, история, 4 года назад, По-английски

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

Полный текст и комментарии »

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

Автор duckduckMoose, история, 4 года назад, По-английски

Hi everyone. I was doing 203C. I managed to solve (link) the problem in O(n*log n) time (constraints: n<10^6). But I got TLE. I checked from the editorial and my approach was correct. I read some comments in the editorial suggesting not to use print function and use other methods to print, so I used 'sys.stdout.write'. But then also the problem isn't resolved. How can I print faster than sys.stdout.write?

Полный текст и комментарии »

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