blue__legend's blog

Help regarding Editorial Interesting trip Hackerrank
By blue__legend, history, 6 years ago, In English

https://www.hackerrank.com/contests/university-codesprint-5/challenges/marmelade-kingdom I am not able to understand the editorial can someone explain a bit in detail.

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

»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

you can easily deduce that the solution is Dynamic Programming where dp[u] equals str[u]  +  the lexicographically minimum dp[v] where there is an edge going from u to v however doing that with strings will easily cause you a very shiny time limit exceeded.

so he is representing the string saved in dp[v] as a segment tree that carries the string hash of a range however finding the minimum between two strings is not that easy hence the hash comes into play he binary search the maximum prefix where hash1[x][0 -  > i] = hash[y][0 -  > i] now the next character should be the one you decide for which is less x or y.

but that is also going to give a very shiny memory limit exceeded before it gives you a time limit exceeded hence the use of persistent segment tree where you can say that tree[u] = update(tree[v]) this assigns the value of tree[v] to tree[u] with the modification that is add str[u] to segment tree of v

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the beautiful explanation. I didn't understand the segment tree part. Are we making separate segment tree for each node? If not then how it is assured that the nodes which have an incoming edge to current nodes are in a sequence.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      yes there is a segment tree for each node that's the idea of persistent segment trees they help you do that efficiently.

      you can read about them here

      → Reply