@ all. what if we use greedy approch..like if we slice when in remaining fruits on screen any one fruit is going to disappear?will it work?
On Friday, February 1, 2013 9:07:14 AM UTC+5:30, emmy wrote: > > Ohk.. I finally got it. > Thanks guys!! > This was great help. > > > On Mon, Jan 28, 2013 at 4:11 PM, Nikhil Karnwal > <[email protected]<javascript:> > > wrote: > >> no ...when u figure out those m matches just sort them ..now let k=[0,m] >> if currently u are assuming that kth match is already sliced then all >> before that k matches are already sliced.and this u can do by moving >> incrementally from 0 to mth matches. >> >> On Mon, Jan 28, 2013 at 1:43 PM, foram lakhani >> <[email protected]<javascript:> >> > wrote: >> >>> by match u mean that number of fruits that overlap with i th fruit but >>> are not sliced before time i. >>> which means we have to consider 2^m cases where m is the maximum number >>> of fruits that overlap with ith fruit. >>> And this we have to do for each fruit. >>> >>> On Mon, Jan 28, 2013 at 12:54 AM, Nikhil Karnwal >>> <[email protected]<javascript:> >>> > wrote: >>> >>>> Actually dp[i] represent the state in which u make a slice at appearing >>>> time of i th fruits.and match represent the overlapping fruits >>>> with i. >>>> so >>>> for each i dp[i]=max(dp[i],dp[j]+match); >>>> for all j=[0,i] and match =overlapped fruits with i which are not >>>> sliced until the cut of j. >>>> Hope this will help. >>>> Thanks >>>> >>>> On Thu, Jan 24, 2013 at 10:18 PM, foram lakhani >>>> <[email protected]<javascript:> >>>> > wrote: >>>> >>>>> Thanx for the reply but I didnt get you. What does dp[i] represent ? >>>>> >>>>> >>>>> On Thu, Jan 24, 2013 at 9:50 PM, sunny <[email protected]<javascript:> >>>>> > wrote: >>>>> >>>>>> take a structure or pair of start time and finish time and then sort >>>>>> the the structure you know the comparator function the for each for >>>>>> each >>>>>> dp[i] select j belongs to (0,i) and then count the overlap value >>>>>> >>>>>> >>>>>> if(j==0) >>>>>> dp[i]=max(dp[i],match); >>>>>> else >>>>>> dp[i]=max(dp[i],dp[j-1]+match); >>>>>> >>>>>> >>>>>> with this recursive relation my code got accepted in .24 sec others >>>>>> approach you mentioned may lead to the TLE >>>>>> >>>>>> On Thursday, January 24, 2013 1:35:38 PM UTC+5:30, emmy wrote: >>>>>>> >>>>>>> please help me with the following problem: >>>>>>> >>>>>>> http://www.spoj.com/problems/**JUICE/<http://www.spoj.com/problems/JUICE/> >>>>>>> >>>>>>> bit mask will require very large memory. >>>>>>> If I sort the intervals in decreasing order of their start time.. I >>>>>>> still cant make it to a dp >>>>>>> If I sort the intervals in decreasing order of their finish times I >>>>>>> am still not getting a recurrence for dp that is valid >>>>>>> If I convert this to an interval graph, I have to find the maximum >>>>>>> number of vertices that can be included in some clique of size >=3. But >>>>>>> this also seems like a brute force approach. >>>>>>> >>>>>>> Which approach to try?? please help!! >>>>>>> >>>>>>> -- >>>>>> >>>>>> >>>>>> >>>>> >>>>> -- >>>>> >>>>> >>>>> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To unsubscribe from this group, send email to >>>> [email protected] <javascript:>. >>>> For more options, visit https://groups.google.com/groups/opt_out. >>>> >>>> >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected] <javascript:>. >>> >>> For more options, visit https://groups.google.com/groups/opt_out. >>> >>> >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected] <javascript:>. >> >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
