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. For more options, visit https://groups.google.com/d/optout.
