aviroop123's blog

How to solve this problem ?
By aviroop123, history, 8 years ago, In English

Problem Link — https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=738&page=show_problem&problem=5931

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

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

Direct the edge from node v to Lv and from Rv to v.

Now the problem becomes "How many ways are there to arrange the vertices such that the arrangement is topologically sorted."

Let dp(v, i) be how many topological sorts with the vertices from v's subtree are there such that there are exactly i vertices behind the vertex v.

Now updating the dp is easy.

→ Reply