pachon's blog

Help with DP speed up technique
By pachon, 10 years ago, In English

Hi Guys

I was reading this document point "2.1. The problem" and I was trying to implement the solution for (point "2.3.1. Leaves") http://vn.spoj.com/problems/NKLEAVES/en/ but I think I am missing something, my implementation fails even with example test case :(. Please, can someone help me with this problem.

Just in case, cij in the document is my function cost(i,j), F[n] is my dp[n][j], g in the document is the same g, but I send an extra parameter j the number of piles.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

This kind of problems can be solved with convex hull trick

I learned this stuff after reading these links :

Codeforces Blog

Wikipeg

And after you solved the example problems in this blogs , i recommend to you try to solve

Arranging Heaps LA 2012

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

    Yes, Arranging Heaps is almost the same problem (but with differents distances), but I am not able to understand the convex hull trick, as a first step I wanted to solve nkleaves unless you want to explain it to me? :D

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

      I think that if you read carefully this links you can learn convex hull trick , i learned for my own reading this articles , if i can do it you can do it.

      This two links have very good explanations.

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

I couldn't understand the second speed up technique mentioned in the pdf document, but can it solve a problem which convex hull trick can't solve? both NKLEAVES and IOI 2002 Batch Scheduling are application for that technique but both can be solved using convex hull trick

→ Reply