Yuo might wanna check out The latest codeforces beta round problem C . On Jan 28, 8:34 pm, nishaanth <[email protected]> wrote: > @All... According to the constraints(SPOJ problem) wont this dp solution > time out ? > > On Tue, Jan 25, 2011 at 12:23 AM, sankalp srivastava < > > > > > > [email protected]> wrote: > > Correct me if I'm wrong > > > dp[i][j]=how many numbers of length i with the last digit j(int base > > 10) > > dp[0][j]=0 > > dp[i][0]=dp[i-1][0] , last digit can't be zero otherwise the number > > has i-1 digits , not j; > > > now the recursion to pass from one state to the next > > > dp[i][j]=dp[i-1][k]+1(for each value of k such that k is less than j , > > from 0 to k) > > That is to say , the number of numbers with length i and last digit > > j , will be equal to the number of numbers with the last digit k , for > > each k less than j .One is added because , we must not have included > > the 0 in the last case , but we will include the zero case here . this > > one corresponds to zero case . > > > Finally , the answer will be > > > dp[n][j] , 1<=j<=9 , sum up all these and u have the answer > > For example for 2 digits > > dp[1][1-9]=1 , as nothing preceeds them and as said in the problem , > > one digit numbers are always increasing/decreasing . > > next dp[2][1]=dp[1][1](As only 1 is less than , equal to 1 , the last > > digit in this state) > > dp[2][2]=dp[1][1]+dp[1][2] =2( 1,2 and 2,2) > > Continuing this way , we will get the answer , may be 50 , though i > > din code it . > > > similarly , for 3 digits > > > Correct me if not! > > > On Jan 25, 12:06 am, juver++ <[email protected]> wrote: > > > dp[i][j] - how many numbers of length i and with the last digit j. > > > Apply the scheme to increasing and decreasing number, then find ratio. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%2Bunsubscribe@googlegroups > > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > S.Nishaanth, > Computer Science and engineering, > IIT Madras.
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
