codeshaker's blog

dp problem : some different version of lis
By codeshaker, 11 years ago, In English

cant figure out the recursive relation to solve it..thnx

problem link : http://www.spoj.com/problems/MSTICK/

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

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

A very interesting problem. Curiously, I think it would have taken me quite a while to figure out a valid approach if you had not mentioned LIS in the title of your post.

Now, I'm not entirely sure what you mean by “recursive relation” (it sounds to me as if maybe you want some kind of formal proof or classic D.P. definition), but if a basic hint is good for you, here's one:

Central to this problem is the issue that each stick is a 2-integer tuple. Consider sorting the list of tuples in the usual way (first by the first element, then by the second element). Now, if the tuples didn't have a second element, the problem would be solved by now and the answer would always be 1, because the list is already sorted by the first element.

So, the question now is: in which cases does the answer get larger? Take your time to think about it if you hadn't considered this perspective. Now, consider two tuples in the sorted list:

(li, wi), (lj, wj) where 0 ≤ i < j < n

Because of the sorting, it's guaranteed that either:

  • li < lj —or..
  • li = lj and wi ≤ wj

There would be only one case in which both tuples couldn't be handled in the same pass of the machine (so the answer could not be 1), and it is when li < lj and wi > wj. Basically, any pair of tuples where i < j and wi > wj in the sorted list is telling us something about a situation in which the answer may need to get larger.

At this point, I'd invite you to spend some time about how the above observations relate to the Longest Decreasing Subsequence problem (or LIS, if you sort the list in the other direction). I think that, with a good understanding of the LIS algorithm, the conclusions should become clear without much effort.

Hope it helps.

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

@lbv thnx for the detailed explanation but i still have a doubt . you said that pai where i<j and w[i]>w[j] this "may" lead to increase in answer . can u give me a test case when it hold. as in my code i just increased the answer whenever I found w[i]>w[i-1] (for i in(1,n-1) and sorted lengthwise previously ) and found another answer similarly which I incresed as I found l[i]>l[i-1](for all i in (1,n-1) and sorted weightwise previously) and then found minimum of both but got wrong answer verdict,, code link :http://ideone.com/G4u26Y

→ Reply