randomusername's blog

Facebook Hacker Cup 2012 Round 2 — Problem Monopoly
By randomusername, 12 years ago, In English

Hi, does anyone know a solution to this problem? I saw some contestants' solutions, but I'm not able to understand everything just from the code.

Thanks

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

»
12 years ago, hide # |
← Rev. 2  
Vote: I like it +6 Vote: I do not like it

First, we use DSU in order to store current companies after each merge. For each company we also store a map: the degree of the root (at most D) to the minimal depth of the tree with that degree. Initially all trees contain 1 vertex and all maps contain the pair (0, 1) only. Calculating this map for a new company after merge is simple: we just trying to connect the first root to the second one and vice versa, for all values of the degree of parent root. In a such way the new degree is increased by 1 and the new depth is at most the minimal depth of child root's tree increased by 1.

→ Reply