what will be the dynamic programming solution to the above problem ? can anyone explain the states of the dp ?
On Mon, Jun 20, 2011 at 6:53 PM, oppilas . <jatka.oppimi...@gmail.com>wrote: > I think you have not read the question carefully. Please read it again and > try to ans for small values of n,k first. > for k=1, answer will be always 1. > > > On Mon, Jun 20, 2011 at 6:31 PM, saurabh singh <saurab...@gmail.com>wrote: > >> O.K can anyone suggest the combinatorial solution.I thought it this way- >> Assume k chairs as one chair.Now no. of ways arranging these chairs would >> be ((n-k+1)-1)! and the number of ways of arranging the k chairs would be >> k!. >> So the no. of ways of arranging the chairs so that they are always >> together becomes..(n-1)!-(n-k)!*(k)!? >> Where was I wrong in the approach?Please correct me, >> >> >> On Mon, Jun 20, 2011 at 5:36 PM, RITESH SRIVASTAV < >> riteshkumar...@gmail.com> wrote: >> >>> @Saurabh >>> Your formula is incorrect. >>> for input : 5 2 >>> the answer should be 5 but your program gives 12 as output. >>> >>> On Jun 19, 11:35 pm, abc abc <may.i.answ...@gmail.com> wrote: >>> > @above Better you ask it on spoj forum >>> > >>> > On Sun, Jun 19, 2011 at 7:27 PM, saurabh singh <saurab...@gmail.com> >>> wrote: >>> > > I am getting WA for this problem.I dont know whether its case of >>> overflow >>> > > or I have come up with a wrong formula, >>> > >https://www.spoj.pl/problems/CHAIR/ >>> > > I am coding in python so I dont think there is probblem of overflow. >>> > >>> > > def f(n): >>> > > if n<0: >>> > > return 0 >>> > > if n==0: >>> > > return 1 >>> > > i=n >>> > > prod=1 >>> > > while i>0 : >>> > > prod*=i >>> > > i-=1 >>> > > return prod >>> > > n=input() >>> > > k=input() >>> > > if k==1: >>> > > print n >>> > > elif 2*k>n: >>> > > print 0 >>> > > else : >>> > > x=f(n-1) >>> > > y=f(n-k)*f(k) >>> > > print (x-y)%1000000003 >>> > >>> > > -- >>> > > Saurabh Singh >>> > > B.Tech (Computer Science) >>> > > MNNIT ALLAHABAD >>> > >>> > > -- >>> > > You received this message because you are subscribed to the Google >>> Groups >>> > > "Algorithm Geeks" group. >>> > > To post to this group, send email to algogeeks@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. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@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. >>> >>> >> >> >> -- >> Saurabh Singh >> B.Tech (Computer Science) >> MNNIT ALLAHABAD >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
