pizza_hot's blog

Can't understand the convex hull trick/optimization
By pizza_hot, history, 8 years ago, In English

Hi Everyone !

I was studying convex hull trick from here

I understood the main idea but I didn't understand the solution for the problem ACQUIRE

My question is :

they sorted rectangles by height in ascending order (if they are equal put the rectangle with the largest weight first)

and this is their pseudo code:

input N
for i=1 to N
     input rect[i].h
     input rect[i].w
let cost[0] = 0
for i=1 to N
     let cost[i] = OO
     for j=0 to i-1
         cost[i] = min(cost[i],cost[j]+rect[i].h*rect[j+1].w)
print cost[N]

but it's not necessary for every j<i : rect[j].w >rect[i].w (because we are comparing by the height first)

can someone tell me why did they do this ? :/

or have you got a better explain for the solution ?

sorry for my bad english , thanks in advance

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

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Read observation 1 about irrelevant rectangles.

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

Suppose that both of rectangle A's dimensions equal or exceed the corresponding dimensions of rectangle B. Then, we may remove rectangle B from the input because its presence cannot affect the answer, because we can merely compute an optimal solution without it and then insert it into whichever subset contains rectangle A without changing the cost.

Since the rectangles are then sorted by height, the width of the rectangles must be strictly decreasing. Otherwise, there exists two adjacent rectangles in the sorted list where the rectangle on the right has both a larger height and a larger width, which is impossible because the rectangle on the left is irrelevant and should have been removed.

→ Reply