@priyanka.. If you are looking for some problem where the same concept has been applied, then go thru the following link... http://groups.google.com/group/algogeeks/browse_thread/thread/0751e67f32266e53#
and look for the explanation and code that has been posted for the following problem: http://www.spoj.pl/problems/NY10E/ [@ Non-Decreasing Digits] On Jan 10, 11:14 pm, Lucifer <sourabhd2...@gmail.com> wrote: > @priyanka.. > > SuperSum(k, n) : > For any given base X representation there will be X digits.. > Now say, the digits are named as A(i) ... such that, > A1 < A2 < A3 < .... < A(X)... > [ all digits being significant ] > > Then SuperSum basically says that what are the no. of (k+1) sized > integers that can formed such that the digits in the integers are in > non-decreasing order from left to right and ends with A(n) where n <= > X... > > For ex - for Base 5, the digits are 1,2,3, 4, 5 > Now SuperSum(1,4) = No. of 2-sized integers that can be formed for > base-5, where the integer ends with at A(4) [ i.e. '4' for base-5].. > ------------------------------ > For simplicity, lets define P(i, j) = SuperSum(i - 1, j).. > > Therefore, > P(k, n) : > the no. of (k) sized integers that can formed such that the digits in > the integers are in non-decreasing order from left to right and ends > with A(n) where n <= X > > Hence, > P(1, i) = 1 > P( k, n ) = P(k-1, 1) + P(k-1, 2) + ....+ P(k-1,n) > i.e. > No. of 'k' sized non-decreasing integers = sum over all i { no. of > 'k-1' sized integers that end at A(i) such that A(i)<= A(n) } > > Now, the P(k, n) equation is nothing but a recurrence equation which > should be obvious based on the above explanation.. > But, P(k, n) is nothing but (n+k-1) C (k).. > i.e > SuperSum(k, n) = (n+k) C (k+1)... > = SuperSum(k-1, n) * (n+k) / (k+1).. > --------------------------------------------------------------------------- > -------- > > Probably the next question would be : > P(k, n) = (n+k-1) C (k) ?? > > Well i will explain it with a short example... > Base-3 : {1, 2 ,3 } > > Size : 1 > Integers ending No. of integers > at 'i' th digit > 1 1 > 2 1 > 3 1 > > Size-2 > Integers ending No. of integers > at 'i' th digit > (1)1 1 > (1)2, (2)2 2 > (1)3, (2)3, (3)3 3 > > // the brackets above indicate that the integers within the bracket > have been used from table 'Size-1' > // Basically we are building table 'Size-n' based on table 'Size- > (n-1)'... > > Also you must observe that the 'no. of digits' column of table > 'Size-2' is nothing > but the cumulative sum of 'no. of digits' column of table 'Size-1'.... > > The 'no. of digits' column of table 'Size-3' would be > 1 > 3 > 6 > The 'no. of digits' column of table 'Size-4' would be > 1 > 4 > 10.. > > Do you observe something ??? > [Remember pascal's triangle...] > ----------------------------------------------------- > > A naive approach would be prove: > SuperSum(k-1, n) = SuperSum(k-1, n) * (n+k) / (k+1) using induction.. > Calculate for SuperSum(1, 1), SuperSum(1, 2),.. SuperSum(1, n) and so > on.. and see how it goes... > Observe the pattern... > ---------------------------------------------- > > On Jan 10, 8:35 pm, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > > > > > @atul > > > First of all, i must say you are really good at catching my "editing > > mistakes" :).. > > > Correction: > > superSum = ( superSum * ( ( n + i )%1000000007 ) ) / (i+1); > > > On Jan 10, 8:29 pm, atul anand <atul.87fri...@gmail.com> wrote: > > > > @Lucifier : your reduced form is not generating right output... > > > remove modulo and calculate for SuperSum(2,3) > > > > On Tue, Jan 10, 2012 at 6:12 PM, priyanka <priyankajag...@gmail.com> > > > wrote: > > > > @lucifier : > > > > Please tell how you reduce SuperSum ( k, n) into > > > > SuperSum(k,n) = SuperSum (k-1, n) * (n+k) / (k+1) > > > > > -- > > > > You received this message because you are subscribed to the Google > > > > Groups > > > > "Algorithm Geeks" group. > > > > To view this discussion on the web visit > > > >https://groups.google.com/d/msg/algogeeks/-/jWq_vujbiCkJ. > > > > > 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.
