faiyaz26's blog

UVA 12440 Solution Idea ?
By faiyaz26, 9 years ago, In English

I am stuck with this problem for more than 2 years. :(

Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3871

Lightoj categorized this problem under DP and Segment tree. But I have no idea how to plug this two topic in the solution. Can anyone provide me the solution in descriptive way? :)

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I found this : http://morris821028.github.io/2014/12/09/uva-12440/ Using google translate i think you can understand most of it. It's a worst-case O(n^2) solution but fast enough to get AC. Then i changed the code to make it O(nlogn) using multiset. http://paste.ofcode.org/HL4mwrQXh8Xk8jZDFNGv3r

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It has been discussed in a previous blog

http://codeforces.net/blog/entry/12393

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain in this solution how do we use segment tree to get min of S(k) + H(k + 1, n)?

    It seems like it's similar to 2D Segment Tree because query has 3 parameters not 2.

    Is there a way to do it in O(logn)?

    → Reply