@Lucifer:
Ya,got it now..thanks a lot! :)
On Thu, Dec 29, 2011 at 7:43 AM, Lucifer <sourabhd2...@gmail.com> wrote:
> @rajat..
>
> First of all.. sorry for the late reply :)
>
> Below i have explained the dp approach by taking.. Once u trace it u
> will be able to understand the code..
>
> Lets denote the no. of digits by K..
>
> Now when K = 1, then the no. of digits that can formed is 10 i.e 0 to
> 9...
>
> Say, P(K) denotes the no. of integers that can be formed using K
> digits..
>
> Hence, when K = 2, the digits would be :
>
> 00 01 02 03 04 05 06 07 08 09 - Line 1
> For simplicity lets remove all leading 0's from Line 1..Hence we will
> get,
>
> 0 1 2 3 4 5 6 7 8 9 - Line 1
> Now, we can assume to put the first integer 0 in a separate line
> called Line 0, as its the only integer whose value is 0 after removing
> all leading 0's.
>
> 0 - Line 0
> 1 2 3 4 5 6 7 8 9 - Line 1
> 11 12 13 14 15 16 17 18 19 - Line 2
> 22 23 24 25 26 27 28 29 - Line 3
> ................continued...
> 88 89
> 99 - Line 10
>
> Total no. of integers from Line 0 to Line 10 = 1+ 9 + 9 + 8 + 7 + ...
> + 1 = 55
>
> Let Q(K) be defined as the no. of integers that can be formed by using
> K digits where each integer has size K.
>
> Hence, we reduce P(K) as shown below:
> P(K) = 1 (for the first 0 integer) + Q(1) + Q(2) + Q(3) + .... + Q(K)
>
> For K=2, as in the above example..
>
> P(2) = 1 + Q(1) + Q(2)
> = 1 + ( 9 ) + (9 + 8 + ...+ 1)
> = 1 + 9 + 45 = 55
>
> If you observe closely then u will see that Q(2) i.e Line 2 to Line 10
> has been generated based on Q(1) i.e Line 1.
>
> Here, is where DP comes into play. If we can find a way to generate
> Q(i) given Q(i-1) then we are done.
>
> // Lets look at array A with 1-based indexing for simplicity
> Now, say if we have an array A[9], such that A[i] is used to keep
> track of no. of integers of size 'L' which start with digit 'i'.
>
> Now, say for size 'L+1' we need to calculate new value for A[9] ( say
> we store the new values in A(new)[9]
> The no. of integers that can be formed of size 'L+1' having the
> leading digit as 9 is same
> as the no. of integers starting with 9 of size 'L'.
> Therefore,
> A(new)[9] = A[9].
>
> Now,
> The no. of integers that can be formed of size 'L+1' having the
> leading digit as 8 is equal to
> the no. of integers starting with 8 of size 'L'
> +
> the no. of integers starting with 9 of size 'L'
>
> A(new)[8] = A[8] + A[9]
>
> Similarly,
> A(new)[1] = A[1] + A[2] + ...+ A[9]
>
> If you observe closely u will see that all we are doing is taking the
> cumulative sum from A[9] to A[1]
>
> Hence, we can modify the same array as follows:
>
> // for size 'L+1', given A which stores the information for size
> 'L'...
> // After executing the following code, A will store information for
> size 'L+1'
> for (int i = 8; i >=1 ; --i)
> A[i] += A[i+1];
>
> Hence, all we need to do is run the for loop for K - 1 times for K>1
> and at the end of each loop record the sum of entire array and add it
> to the totalSum. Also add 10 to totalSum at the beginning of the
> entire algo, as we know that for K=1 the no. of integers are 10..
>
> Now array A needs to be initialized as follows:
>
> Q(1) = 9 and the corresponding array values would be as follows:
>
> A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
> 1 1 1 1 1 1 1 1 1
>
> Now, Q(2) = 45 and the corresponding array values would be as follows:
>
> A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
> 9 8 7 6 5 4 3 2 1
>
> Q(3) = 165 and the corresponding array values would be as follows:
>
> A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
> 45 36 28 21 15 10 6 3 1
>
> // Q(i) is nothing but the sum of the entire array..
>
> Hence, P(3) = 10 ( 1+ 9 for K =1) + 45 ( Q(2) ) + 165 ( Q(3) )
> = 220.
>
> ------------------------------------------
>
> On Dec 28, 1:21 pm, sourabh singh <singhsourab...@gmail.com> wrote:
>> @All are these output's correct ??
>>
>> 288230376151711744 20164264869698944
>> 144115188075855872 5130634330054016
>> 72057594037927936 5130634330054016
>> 36028797018963968 1306288411057536
>> 18014398509481984 1306288411057536
>> 9007199254740992 332818957147520
>> 4503599627370496 332818957147520
>> 2251799813685248 84859707399552
>> 1125899906842624 84859707399552
>> 562949953421312 21654400343424
>> 281474976710656 21654400343424
>> 140737488355328 5530598972800
>> 70368744177664 5530598972800
>> 35184372088832 1413883960704
>> 17592186044416 1413883960704
>>
>> On Tue, Dec 27, 2011 at 11:20 PM, sourabh singh
>> <singhsourab...@gmail.com>wrote:
>>
>>
>>
>>
>>
>>
>>
>> > @all
>>
>> > plz point out wat's wrong with this code. works for small numbers but
>> > fails for large number's
>>
>> > #include<conio.h>
>> > #include<iostream>
>> > using namespace std;
>> > unsigned int find_nCp(unsigned int n,unsigned int p)
>> > { unsigned int j=p;
>> > unsigned int num=1,den=1;
>> > for(;j;j--)
>> > num*=n--;
>> > for(;p;p--)
>> > den*=p;
>> > return (num/den);
>> > }
>>
>> > unsigned int num(unsigned int n,unsigned int k)
>> > {
>> > if(n==1 || k==0)
>> > return 1;
>> > return find_nCp(n,k) + num(n-2,(n-1)/2);
>> > }
>> > main()
>> > { uint64_t n,p,test=1;
>> > unsigned int t,i,sum,j;
>> > scanf("%u",&t);
>> > while(t--)
>> > { n=test<<t;
>> > scanf("%llu",&n);
>> > if(n<4)
>> > cout<<0<<endl;
>> > else
>> > { for(p=1,i=0;p<=n;p=p<<1,i++);
>> > i=i-2;
>> > if(i%2==0)
>> > {
>> > i--;
>> > }
>> > cout<<num(i,i/2)<<endl;
>> > getch();
>> > }
>> > }
>> > return 0;
>> > }
>>
>> > On Tue, Dec 27, 2011 at 10:33 AM, kumar rajat
>> > <thebossku...@gmail.com>wrote:
>>
>> >> *I am not able to follow..
>>
>> >> On Tue, Dec 27, 2011 at 11:47 PM, kumar rajat <thebossku...@gmail.com>
>> >> wrote:
>> >> > @Lucifier:
>> >> > Thanks a lot..
>> >> > But,I am able to follow the code that u posted for Non-Decreasing
>> >> Digits.
>> >> > Can u jus explain ur algo instead of givin the code directly?
>> >> > Thanks once again.
>>
>> >> > On Tue, Dec 27, 2011 at 10:44 PM, Lucifer <sourabhd2...@gmail.com>
>> >> wrote:
>> >> >> @ Special Nos..
>> >> >> Well the actual logic would be :
>> >> >> int count = 0;for ( int i = 2; i <= LOGbase2(N) ; i+=2) count+=
>> >> >> [ (i-1) C (i/2) ] ; // here xCy is nothing but the no. of ways y items
>> >> >> can be selected from a collection of x items.
>> >> >> Hence, the working code:
>> >> >> int totalCount = 0;
>> >> >> int interCnt = 1;
>>
>> >> >> if ( LOGbase2(N) > 1)
>> >> >> {
>> >> >> totalCount = 1; // for LOGbase2(N) = 2...
>>
>> >> >> for ( int i = 4; i <= LOGbase2(N) ; i+=2)
>> >> >> {
>> >> >> interCnt = (i-1)*(i-2) * interCnt / ( i/2 * (i/2 -1));
>> >> >> totalCount += interCnt;
>>
>> >> >> }
>> >> >> printf("%d", totalCount);
>> >> >> }
>> >> >> else
>> >> >> printf("%d", 0);
>> >> >> On Dec 27, 7:38 pm, Tasvinder Singh <tasvinde...@gmail.com> wrote:
>> >> >>> I think the first problem involves some mathematics...
>> >> >>> In this we fix the first bit and if the remaining no. of bits are odd
>> >> then
>> >> >>> we calculate the no. as follows
>>
>> >> >>> If we have 2^4=16 then total bits 5 so we do not include this.
>> >> >>> Total no. of bits in one less than the given no. (in this eg. 15) is
>> >> 4.
>> >> >>> Fix first bit, no. of bits remaining = 3
>> >> >>> Now let 2 bits are 0 and one bit 1. We have total 3!/(2!*1!) = 3
>> >> >>> combinations.
>>
>> >> >>> Now go for next even no which is 2 in this case again do the same
>> >> >>> Fix first bit, no. of bits remaining = 1
>> >> >>> Now let 1 bit is 0. We have total 1!/(0!*1!) = 1 combinations.
>>
>> >> >>> Next even 0. stop here.
>> >> >>> You can go for this by starting from 2 till no. is less than given N
>>
>> >> >>> On Tue, Dec 27, 2011 at 7:28 PM, kumar rajat <thebossku...@gmail.com>
>> >> wrote:
>> >> >>> > Hi
>> >> >>> > I have jus started to learn DP and I have coded the standard
>> >> >>> > algorithms(LCS,etc).
>> >> >>> > I have been trying these problems in SPOJ:
>>
>> >> >>> >http://www.spoj.pl/problems/NOVICE63/
>> >> >>> >http://www.spoj.pl/problems/NY10E/
>>
>> >> >>> > I understand these may be solved elegantly using DP,but I dont get
>> >> to
>> >> >>> > code the same.
>> >> >>> > Can any1 help me how to solve these types of problems using DP?
>> >> >>> > Any help regarding the same will be greatly appreciated.
>>
>> >> >>> > --
>> >> >>> > 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.
>>
>> >> >>> --
>> >> >>> Tasvinder Singh
>> >> >>> B.Tech Final Year,
>> >> >>> Department of Computer Engineering,
>> >> >>> Malaviya National Institute Of Technology, Jaipur.
>> >> >>> Contact: +91-9460627331
>>
>> >> >> --
>> >> >> 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.
