Another approach: Every solution is characterized by: the initial time you put the first candy in box n. All solution yields to ONE of such characterization. It is a class partition of solutions.
Then, start finding or enumerating that classes. Then, remove the assigned candy. Now you have at most n boxes, with one less candy to put in, and with new initial open time Start again. Angel "Java" Lopez @ajlopez On Sat, May 3, 2014 at 8:56 AM, ###@shishir@#### <[email protected]>wrote: > i dunt think.. approach suggested by Angel Java Lopez will work. The > question is related with number of ways to fill the candi box. > After looking at the problem statement .. it is simply activity selection > problem <http://en.wikipedia.org/wiki/Activity_selection_problem>. > Here you have to keep counter for all possible way to achieve varying > variants with 'c-(end[i]-start[i])'. I think.. now it became easy to solve. > > Shishir Gupta > Mumbai, > +91-9503971983 > > > On Sat, May 3, 2014 at 3:07 PM, Angel Java Lopez <[email protected]>wrote: > >> I don't know about polynomial time.... but I should start filling the >> boxes with min(et-st-c), that is, exploring all the branches in a tree >> assigning time to those boxes first. >> >> Angel "Java" Lopez >> @ajlopez >> >> >> On Sat, May 3, 2014 at 6:22 AM, vivek dhiman <[email protected]>wrote: >> >>> Is there a way to solve this problem in polynomial time?? >>> >>> You work in a candy factory. There are n Candy Boxes to fill. >>> You can fill only 1 candy in any of the boxes in 1 second. Each Candy >>> Box has it's own capacity c. >>> Also each candy box has an automatic opening. Each box has a start time >>> 'st' after which only you can start filling the candy in the box. Also each >>> box has an end time 'et' after which you cannot fill the box. >>> also given that for each box: et-st >= c >>> >>> For given n Candy Boxes with start time and end time, find out all >>> possible ways in which we can fill the 'n' boxes successfully. Number of >>> candies are infinite. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Google Code Jam" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> To post to this group, send email to [email protected]. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/google-code/CABaJBv%2Bs2CxJn9LSRwoQzhpKWV2MzAShy1%2ByTkOBVqdvuCuagg%40mail.gmail.com<https://groups.google.com/d/msgid/google-code/CABaJBv%2Bs2CxJn9LSRwoQzhpKWV2MzAShy1%2ByTkOBVqdvuCuagg%40mail.gmail.com?utm_medium=email&utm_source=footer> >>> . >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To post to this group, send email to [email protected]. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/google-code/CAMs%2BDq%2Bkkhpk1Zw2z2xgiLtCQzT5e9NXD4XjRj_cVVypmxg5pg%40mail.gmail.com<https://groups.google.com/d/msgid/google-code/CAMs%2BDq%2Bkkhpk1Zw2z2xgiLtCQzT5e9NXD4XjRj_cVVypmxg5pg%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> >> For more options, visit https://groups.google.com/d/optout. >> > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CAGaVxPGHMV7xhat7aGhnhVaS8-CxckKnA2ra21K1ZnctuExQQg%40mail.gmail.com<https://groups.google.com/d/msgid/google-code/CAGaVxPGHMV7xhat7aGhnhVaS8-CxckKnA2ra21K1ZnctuExQQg%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMs%2BDqKz_R%3Dq3Kw8vA%2BT18pBAsySJ796NpDREj_DZDvHTT0HQw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
