dp(int chair,int person,bool previous)
if(previous)
dp(chair-1,person,0)
else
dp(chair-1,person-1,1)+dp(chair-1,person,0)
with basic conditions.... as it is a circle.. if person is placed in first
chair u cant place a person in last chair
On Tue, Jun 21, 2011 at 7:38 PM, shady <sinv...@gmail.com> wrote:
> 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.
>
--
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.
