NO its not 2^m ,,, you have to use sorting technique .....generally we t do such sorting thing in time interval scheduling(standard greedy problem).....in case you didn,t understand let me know ...
On Monday, January 28, 2013 1:43:35 PM UTC+5:30, emmy 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 > <sunny...@gmail.com<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 >> <foraml...@gmail.com<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 <sharad...@gmail.com<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 >> algogeeks+...@googlegroups.com <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, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
