aviroop123's blog

How to solve this problem ?
By aviroop123, history, 6 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

»
6 years ago, # |
← 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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't understand your approach very clearly ... I have understood how you have reduced the problem to number of ways to order the vertices that are topologically sorted. But I didn't get what your dp state represents. Can you explain your dp state more clearly and the recurrence ?

    → Reply