vrqq's blog

Codeforces 1247 F. Tree Factory
By vrqq, history, 7 years ago, In English

Hit point: To prove these ideas:

  • for some node P, all node in the subtree of Node p are appearing consecutive in bamboo tree.
  • We named the consecutive nodes built up a section in bamboo tree.
  • If node-A have three child: P, Q, R. The section of P, Q, R will range one by one in bamboo tree: A,[P],[Q],[R] or A[Q][R][P] or ...
  • We assume 2 scenario:
    • The right answer of bamboo is A,[P],[Q],[R]. The number of steps we move [Q] to A + defragment [P]
    • The right answer of bamboo is A,[Q],[P],[R]. The number of steps we move [Q] to A + defragment [P]
    • Are equal.

An easy reading graphic and code are on my blog : https://blog.vrqq.org/archives/520/ (With Chinese explanation)

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

»
7 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Take a look on my solution 63512570. It uses straight forward algo to build a tree from a bamboo, using a fact that we should append to bamboo vertex with least maximal tree depth. And then we do a dfs-like travel through the tree and add those vertices to bamboo. Then using some number of operations to move this vertex before we have desired tree. IMHO, this is much simpler than your approach. And much less code

→ Reply