@Divesh, Can you please check the method present in Art_of_Programming_Contest_SE_for_uva.pdf for LIS nlogn (nlogk, k is the size of longest increasing sequence) page number 129 ?.
(1,2) (2,13) (5,10) (7,9)(9,1) In this case, longest sequence is of length two and possible solutions are below, (1, 2), (2, 13) (1, 2), (5, 10) (1, 2), (7, 9) Please let me know if does not work. Thanks, Sathaiah On Thu, Sep 30, 2010 at 2:20 PM, Gönenç Ercan <gon...@gmail.com> wrote: > I really liked Rahul's formulation; is it possible to solve a similar > problem of finding Minimum number of envelopes (may be to save some > stamps) to send all the envelopes with the graph representation? Maybe > by using maximum flow to solve "Minimum path cover in directed acyclic > graph", or am I missing a point? > > On Sep 30, 11:43 am, Gönenç Ercan <gon...@gmail.com> wrote: > > One thing to note is that, this graph is a directed acyclic graph, > > since by definition there can be no edge from a smaller or equal sized > > envelope to a large one. In this setting it is possible to find the > > longest path, by a topological sort and dynamic programming in linear > > time O(V+E). Funny though If it wasn't "strictly smaller" than finding > > the longest path would be NP-Complete. > > > > On Sep 28, 9:03 pm, Rahul Singal <rahulsinga...@gmail.com> wrote: > > > > > > > > > A possible solution i can think is create a directed graph where each > > > vertex is a envelope and edges are from a bigger envelope to smaller > > > envelope ( one which can fit in bigger envelope ) . Now the problem is > > > reduce to finding longest path in the graph . > > > > > Regards > > > Rahul > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
